Effective solutions for the capacitated vehicle routing problem and for the split delivery vehicle routing problem with time windows. (c2013)

Abstract

The Vehicle Routing Problem (VRP) is a generalization of the traveling salesman problem, and was initially proposed by Dantzig in order to find the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal. Various variations of the VRP have been proposed such as the Capacitated VRP (CVRP) where all the customers correspond to deliveries and the demands are deterministic, known in advance, and may not be split. The vehicles are identical and based at a single central depot, and only the capacity restrictions for the vehicles are imposed. The objective is to minimize a weighted function of the number of routes and their travel time while serving all customers. Other Variations add pickup and delivery constraints (VRPPD), time windows constraints (VRPTW) and split delivery constraints (SDVRP). The Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) combines the two main sub problems (SDVRP) and (CVRPTW). In this work, we present efficient solutions for solving the CVRP as well as the SDVRPTW, two combinatorial optimization problems. The algorithm starts with a greedy selective method that generates an initial solution then improves the solution using a combination of random and deterministic moves that are based on problem knowledge information. Experimental results are presented and favorable comparisons are reported.