Two Novel Heuristics Based on a New Density Measure for Vehicle Routing Problem

Introduction

The Vehicle Routing Problem (VRP), proposed by Dantzig and Ramser (1959), is an important research area in operations research given its importance in logistic planning. The use of route planning and scheduling algorithms can help to save time and shipping costs. VRP is an extension of the well-known TSP problem with several vehicles, and each customer has a demand less than the vehicle capacity. All the vehicles start from one or several depots and finish their travels at the same start depot after visiting a set of customers (Figure 1). The aim is to find the best route for each vehicle in order to minimize the total distance traveled by all the vehicles, subject to a set of constraints like vehicle capacity, time, pickup and delivery, etc. Although the problem appears to be easy to state, it belongs to NP-hard problems category, and needs a huge time and space to resolve, especially with complex VRP instances (Toth & Vigo, 2002; Samanta & Jha, 2011).

There are several variants of VRP. Each one of these variants differs from another by constraints or features that have to be taken into account. The basic variant of VRP problem is the Capacitated Vehicle Routing Problem (CVRP), in which only the capacity constraint is considered (Laporte & Semet 2001; Charikar, Khuller & Raghavachari, 2001). In the CVRP, there is only one depot from which all the vehicles stars. Each vehicle has a limited capacity cap. There are a set of n customers and each customer has a certain demand d < cap. Each customer is served by one vehicle, and the total demand carried by one vehicle is at most cap. Consequently, the solution of CVRP is a set of routes with the lowest cost.

Figure 1.

A simple VRP example

In order to solve the CVRP, several methods were proposed that we can classify in tow main classes exact algorithms and approximate algorithms. The exact algorithms are able to find the exact solution of the CVRP. The most popular algorithms of this class are based on the Branch & Bound (Toth & Vigo, 2001), Branch & Cut (Lysgaard, Letchford & Eglese, 2004), column generation (Baldacci & Mingozzi, 2009), and set partitioning (Baldacci, Christofides, & Mingozzi, 2008). Unfortunately, the exact algorithms have an exponential complexity, and they are impracticable for large CVRP instances (Samanta & Jha, 2011). On the other hand, the approximate algorithms constitute an alternative way to find near optimal solutions in reasonable time compared to the exact algorithms. The approximate algorithms can be divided into three subclasses: constructive heuristics, improvement heuristics and metaheuristics. The constructive heuristics gradually build a feasible solution. The main features of the constructive heuristics are the simplicity and the rapidity to find quite acceptable solutions. The most known and used heuristics for CVRP are the savings heuristic of Clarke and Wright (Clarke & Wright, 1964), the sweep algorithm (Gillett & Miller, 1974), the insertion heuristic (Campbell & Savelsbergh, 2004), the petal algorithm (Ryan, Hjorring & Glover, 1993), and the nearest neighbor algorithm.

The main disadvantage of heuristics is the fact that they do not guarantee the optimality, and sometimes the solutions are too far from the best solutions. In order to improve the quality of the heuristic solutions, improvement heuristics are used (Kinderwater & Savelsbergh, 1997). The improvement heuristics try to find an enhanced solution from an initial solution created by a construction heuristic.