The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation |
| |
| Affiliation: | 1. Graduate Program in Electrical Engineering, Federal University of Minas Gerais, Av. Antônio Carlos 6627, 31270-901 Belo Horizonte, MG, Brazil;2. Department of Electrical Engineering, Universidade Federal de Minas Gerais, UFMG, Belo Horizonte, Brazil;3. Departamento de Computação e Sistemas, Universidade Federal de Ouro Preto, UFOP, João Monlevade, MG, Brazil;4. Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport (CIRRELT), Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal, Québec, Canada H3C 3J7;1. Department of Industrial Engineering, Ferdowsi University of Mashhad, 91775-1111, Mashhad, Iran;2. DEI, University of Bologna, Viale Risorgimento 2, 40136, Bologna, Italy |
| |
| Abstract: | The multi-depot fleet size and mix vehicle routing problem, also known as the multi-depot routing with heterogeneous vehicles, is investigated. A mathematical formulation is given and lower as well as upper bounds are produced using a three hour execution time of CPLEX. An efficient implementation of variable neighborhood search that incorporates new features in addition to the adaptation of several existing neighborhoods and local search operators is proposed. These features include a preprocessing scheme for identifying borderline customers, a mechanism that aggregates and disaggregates routes between depots, and a neighborhood reduction test that saves nearly 80% of the CPU time, especially on the large instances. The proposed algorithm is highly competitive as it produces 23 new best results when tested on the 26 data instances published in the literature. |
| |
| Keywords: | Multi-depot vehicle routing Heterogeneous vehicles Distribution network ILP formulation Variable neighborhood search |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
