Exact algorithms for a selective Vehicle Routing Problem where the longest route is minimized |
| |
| Institution: | 1. School of Physics & Material Science, Anhui University, Hefei, 230039, China;2. School of Physics & Electronics Science, Fuyang Normal College, Fuyang, 236037, China;1. Center for Cosmic Origins and Department of Physics and Astronomy, Dartmouth College, Hanover, NH 03755, USA;2. Department of Physics, McGill University, Montréal, QC, H3A 2T8, Canada;3. Center for Field Theory and Particle Physics & Department of Physics, Fudan University, 200433 Shanghai, China;1. PARADISE Research Laboratory, University of Ottawa, Ottawa, ON, Canada;2. Department of Computer Science, Federal University of Minas Gerais, Brazil;1. Institut für Optimierung und Operations Research, Universität Ulm, D-89069 Ulm, Germany;2. PESC, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil;1. Department of Physics, University of Jyväskylä, P.O. Box 35, FI-40014 University of Jyväskylä, Finland;2. Helsinki Institute of Physics, University of Helsinki, P.O. Box 64, FI-00014, Finland;3. Departamento de Física de Partículas and IGFAE, Universidade de Santiago de Compostela, E-15782 Galicia, Spain |
| |
| Abstract: | In this paper, we study a non-capacitated Vehicle Routing Problem (VRP) where not necessarily all clients need to be visited and the goal is to minimize the length of the longest vehicle route. An Integer Programming Formulation, a Branch-and-cut (BC) method and a Local Branching (LB) framework that uses BC as the inner solver are presented. Sharper upper bounds are obtained by LB, when the same time limit was imposed on the execution times of both approaches. Our results also suggest that the min-max nature of the objective function combined with the fact that not all vertices need to be visited make such problem very difficult to solve. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
