THE ROBUST VEHICLE ROUTING PROBLEM: AN APPLICATION OF THE TRAVELING SALESMAN PROBLEM WITH CENTER

Abstract

The objective of the vehicle routing problem (VRP) is to determine minimum distance routes for one or more vehicles, operating from one or more depots, serving a set of customers with non-zero demand, subject to constraints including but the number of vehicles, vehicle capacity, and distance per route. A large research literature exists for the VRP due to the difficulty of the problem and its wide applicability to real-world business operations, such as package delivery.

The objective of the robust vehicle routing problem (RVRP) is to find the shortest possible nominal routes for a set of vehicles operating from a single depot over a number of days. The number of customers assigned to each route is subject to increase or decrease via the exchange of customers between the routes. We describe this variant of the traditional VRP and provide test instances. We give a general solution procedure for the problem based on generating sets of candidate solutions, from which we select the best. We describe and evaluate several candidate solution generation approaches and identify one that consistently yields high quality solutions with reasonable solution times.