The challenge of solving various vehicle routing variants with a unified variable neighborhood search

Description

Vehicle routing problems (VRPs) are meaningful problems in real-life distribution management. Most of the algorithms for VRPs reported in the literature are used to solve one specific VRP. Normally, different variants ask for different parameter settings or even different approaches. In this work, a unified variable neighborhood search (UVNS) framework using simple shaking and local search strategies is developed to solve different vehicle routing variants with a fixed fleet size and one parameter configuration; it yields high quality solutions for all considered problems. The generic metaheuristic is applied to a variety of VRPs: the capacitated VRP, the open VRP (OVRP), the VRP with hard and soft time windows, the OVRP with hard and soft time windows, and the time-dependent VRP with hard and soft time windows. In all cases, the vehicles are capacitated and the fleet is homogeneous, and in some instances, route length restrictions must be considered. In addition, in the OVRPs, the vehicles do not return to the depot after the last customer has been serviced. The problems with no time windows or hard time windows are distinguished from the problems with soft time windows: In the former case, the objective is to minimize the total travel time; in the latter case, the objective is to minimize the sum of the total travel time and tardiness across all customers. The tactical and operational problems are usually solved in lexicographical order: minimizing the fleet size first, then the travel cost. Firms also face a daily operation problem, without a decision about the fleet size, which is known at the beginning of each day. That is, real-world daily operation problems require a high quality solution that uses the available vehicles. Therefore, for this research, we seek a solution that minimizes the total travel cost, assuming a fixed fleet of vehicles. Based on the UVNS, a numerical study that discusses several adaptive strategies is presented.

Period	13 Dec 2013
Event title	Annual Workshop of the Austrian Working Group on Metaheuristics
Event type	Conference
Location	AustriaShow on map