Article ID: | iaor20172569 |
Volume: | 24 |
Issue: | 6 |
Start Page Number: | 1233 |
End Page Number: | 1252 |
Publication Date: | Nov 2017 |
Journal: | International Transactions in Operational Research |
Authors: | Potvin Jean-Yves, Gendreau Michel, Hernandez Florent |
Keywords: | combinatorial optimization, optimization, heuristics, management, scheduling, programming: multiple criteria |
In this study, we consider a tactical problem where a time slot schedule for delivery service over a given planning horizon must be selected in each zone of a geographical area. A heuristic search evaluates each schedule selection by constructing a corresponding tactical routing plan of minimum cost based on demand and service time estimates. At the end, the schedule selection leading to the best tactical routing plan is selected. The latter can then be used as a blueprint when addressing the operational problem (i.e., when real customer orders are received and operational routes are constructed). We propose two heuristics to address the tactical problem. The first heuristic is a three‐phase approach: a periodic vehicle routing problem (PVRP) is first solved, followed by a repair phase and a final improvement phase where a vehicle routing problem (VRP) with time windows is solved for each period of the planning horizon. The second heuristic tackles the problem as a whole by directly solving a PVRP with time windows. Computational results compare the two heuristics under various settings, based on instances derived from benchmark instances for the VRP with time windows.