A branch-and-cut approach for the vehicle routing problem with loading constraints |
| |
| Affiliation: | 1. School of Informatics, Reutlingen University, Alteburgstr. 150, 72762 Reutlingen, Germany;2. Computer Languages and Systems Dept., University of Seville, 41012 Seville, Spain;1. Department of Logistics and Forwarding, Széchenyi István University, Egyetem tér 1, Győr 9026, Hungary;2. Department of Automation, Széchenyi István University, Egyetem tér 1, Győr 9026, Hungary;1. Institute of Intelligent Systems and Numerical Applications in Engineering, University of Las Palmas de Gran Canaria, 35017 Las Palmas de Gran Canaria, Spain;2. Optimisation Research Group, NICTA, Eveleigh, NSW 2015, Australia;3. Aviation Academy, Amsterdam University of Applied Sciences, Amsterdam 1097 DZ, Netherlands;4. Computer Science Department-IN3, Open University of Catalonia, Barcelona 08018, Spain;1. Pontificia Universidad Católica de Chile, Chile;2. CIRRELT and Canada Research Chair in Integrated Logistics, Université Laval, Canada;3. Department of Economics and Management, University of Brescia, Italy;1. Department of Management Science & Technology, Athens University of Economics and Business, Greece;2. School of Chemical Engineering, National Technical University of Athens, Greece\n |
| |
| Abstract: | In this paper we describe a branch-and-cut algorithm for the vehicle routing problem with unloading constraints. The problem is to determine a set of routes with minimum total cost, each route leaving a depot, such that all clients are visited exactly once. Each client has a demand, given by a set of items, that are initially stored in a depot. We consider the versions of the problem with two and tri dimensional parallelepiped items. For each route in a solution, we also need to construct a feasible packing for all the items of the clients in this route. As it would be too expensive to rearrange the vehicle cargo when removing the items of a client, it is important to perform this task without moving the other client items. Such packings are said to satisfy unloading constraints.In this paper we describe a branch-and-cut algorithm that uses several techniques to prune the branch-and-cut enumeration tree. The presented algorithm uses several packing routines with different algorithmic approaches, such as branch-and-bound, constraint programming and metaheuristics. The careful combination of these routines showed that the presented algorithm is competitive, and could obtain optimum solutions within significantly smaller computational times for most of the instances presented in the literature. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
