A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints

A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints

0.00 Avg rating0 Votes
Article ID: iaor200969297
Country: United States
Volume: 51
Issue: 1
Start Page Number: 4
End Page Number: 18
Publication Date: Jan 2008
Journal: Networks
Authors: , , ,
Keywords: heuristics: tabu search
Abstract:

This article addresses the well-known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two-dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two-dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L-CVRP, is NP-hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch-and-bound procedure. The effectiveness of the algorithm is demonstrated through extensive computational experiments.

Reviews

Required fields are marked *. Your email address will not be published.