Reachability cuts for the vehicle routing problem with time windows |
| |
| Institution: | 1. CIRRELT - Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Université de Montréal, P.O. Box 6128, Station Centre-Ville, Montréal H3C 3J7, Canada;2. School of Management, Université du Québec à Montréal, P.O. Box 8888, Station Centre-Ville, Montréal H3C 3P8, Canada;3. Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal, P.O. Box 6079, Station Centre-ville, Montréal H3C 3A7, Canada;1. Department of Industrial Systems Engineering and Management, National University of Singapore, 1 Engineering Drive 2, 117576, Singapore;2. Red Jasper Consulting Pte Ltd, Singapore;3. City University of Hong Kong Shenzhen Research Institute (CityUSRI), Shenzhen, China |
| |
| Abstract: | This paper introduces a class of cuts, called reachability cuts, for the Vehicle Routing Problem with Time Windows (VRPTW). Reachability cuts are closely related to cuts derived from precedence constraints in the Asymmetric Traveling Salesman Problem with Time Windows and to k-path cuts for the VRPTW. In particular, any reachability cut dominates one or more k-path cuts. The paper presents separation procedures for reachability cuts and reports computational experiments on well-known VRPTW instances. The computational results suggest that reachability cuts can be highly useful as cutting planes for certain VRPTW instances. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
