A branch-and-price approach for a multi-period vehicle routing problem |
| |
| Affiliation: | 1. CIRRELT – Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, École de Technologie Supérieure de Montréal, Canada;2. CIRRELT – Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, and Département de mathématiques et génie industriel, École Polytechnique de Montréal, Canada;3. CIRRELT – Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, and Département de management et de technologie, Université du Québec à Montréal, Canada;4. GERAD – Group for Research in Decision Analysis, and Département de mathématiques et génie industriel, École Polytechnique de Montréal, Canada;5. Département de génie de la construction, École de Technologie Supérieure de Montréal, Canada;1. Department of Computer Science and Information Engineering, National Chin-Yi University of Technology, Taichung, Taiwan;2. Department of Information Management, Kun Shan University, Tainan, Taiwan;1. Ecole Polytechnique de Montréal and Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport, C.P. 6128, Succ. Centre-ville, Montréal, Québec H3C 3J7, Canada;2. Ecole des Mines de Saint-Etienne, CMP, Georges Charpak, Gardanne F-13541, France;3. LIRMM UMR 5506, 161 rue Ada, Montpellier 34392, France;4. Irstea UMR ITAP, 361 rue JF Breton, Montpellier, France;1. Department of Economics and Management, Università di Brescia, Brescia, Italy;2. Department of Statistics and Operations Research, Universitat Politècnica de Catalunya, Barcelona Graduate School of Mathematics, Barcelona, Spain;3. Department of Statistics and Operations Research, Universitat Politècnica de Catalunya, Barcelona, Spain |
| |
| Abstract: | In this paper, we consider tactical planning for a class of multi-period vehicle routing problems (MPVRP). This problem involves optimizing daily product collections from several production locations over a given planning horizon. In this context, a single routing plan for the whole horizon must be prepared, and the seasonal variations in the producers’ supplies must be taken into account. Production variations over the horizon are approximated using a sequence of periods, each corresponding to a production season, while the intra-period variations are neglected. We propose a mathematical model that is based on the two-stage a priori optimization paradigm. The first stage corresponds to the design of a plan which, in the second stage, takes the different periods into account. The proposed set partitioning-based formulation is solved using a branch-and-price approach. The subproblem is a multi-period elementary shortest path problem with resource constraints (MPESPPRC), for which we propose an adaptation of the dynamic-programming-based label-correcting algorithm. Computational results show that this approach is able to solve instances with up to 60 producers and five periods. |
| |
| Keywords: | Multi-period vehicle routing problem Branch-and-price Seasonality Tactical planning |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
