Paper Info
Title
Branch-and-Price for Personalized Multiactivity Tour Scheduling
Abstract
AbstractThis paper presents a branch-and-price approach to solve personalized tour-scheduling problems in a multiactivity context. Two formulations are considered. In the first, columns correspond to daily shifts that are modeled with context-free grammars, and tours are assembled in the master problem by means of extra constraints. In the second formulation, columns correspond to tours that are built in a two-phase procedure. The first phase involves the composition of daily shifts; the second assembles those shifts to generate tours using a shortest path problem with resource constraints. Both formulations are flexible enough to allow different start times, lengths, and days-off patterns, as well as multiple breaks and continuity and discontinuity in labor requirements. We present computational experiments on problems dealing with up to five work activities and a one-week planning horizon. The results show that the second formulation is stronger in terms of its lower bound and that it is able to find high-quality solutions for all instances with an optimality gap lower than 1%.
Year
DOI
Venue
2016
10.1287/ijoc.2015.0683
Periodicals
Keywords
Field
DocType
multiactivity tour scheduling problem, branch and price, context-free grammars, shortest path problem with resource constraints
Rule-based machine translation,Mathematical optimization,Time horizon,Context-free grammar,Shortest path problem,Upper and lower bounds,Scheduling (computing),Discontinuity (linguistics),Branch and price,Mathematics
Journal
Volume
Issue
ISSN
28
2
1526-5528
Citations 
PageRank 
References 
4
0.46
17
Authors
3
Name
Order
Citations
PageRank
Maria I. Restrepo140.46
Bernard Gendron268849.92
Louis-Martin Rousseau388863.71