A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls |
| |
Affiliation: | 1. College of Management, Chongqing University of Technology, Chongqing 400054, China;2. DEI, University of Bologna, Cesena, Italy;3. College of Mechanical Engineering, Chongqing University, Chongqing, China;1. School of Management, Technical University of Munich, Arcisstraße 21, München 80333, Germany;2. Ingolstadt School of Management, Catholic University of Eichstätt-Ingolstadt, Auf der Schanz 49, Ingolstadt 85049, Germany |
| |
Abstract: | We consider an extension of the capacitated Vehicle Routing Problem (VRP), known as the Vehicle Routing Problem with Backhauls (VRPB), in which the set of customers is partitioned into two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. VRPB is known to be NP-hard in the strong sense, and many heuristic algorithms were proposed for the approximate solution of the problem with symmetric or Euclidean cost matrices. We present a cluster-first-route-second heuristic which uses a new clustering method and may also be used to solve problems with asymmetric cost matrix. The approach exploits the information of the normally infeasible VRPB solutions associated with a lower bound. The bound used is a Lagrangian relaxation previously proposed by the authors. The final set of feasible routes is built through a modified Traveling Salesman Problem (TSP) heuristic, and inter-route and intra-route arc exchanges. Extensive computational tests on symmetric and asymmetric instances from the literature show the effectiveness of the proposed approach. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|