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

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

Abdesslem Layeb (Department of Information and Applications, University of Constantine II, Constantine, Algeria)
DOI: 10.4018/ijoris.2015010106


The vehicle routing problem (VRP) is a known optimization problem. The objective is to construct an optimal set of routes serving a number of customers where the demand of each customer is less than the vehicle' capacity, and each customer is visited exactly once like in TSP problem. The purpose of this paper is to present new deterministic heuristic and its stochastic version for solving the vehicle routing problem. The proposed algorithms are inspired from the density heuristic of knapsack problem. The proposed heuristic is based on four steps. In the first step a density matrix (demand/distance) is constructed by using given equations. In the second step, a giant tour is constructed by using the density matrix; the customer with highest density is firstly visited, the process is repeated until all customers will be visited. In the third phase, the split procedure is applied to this giant tour in order to get feasible routes subject to vehicles capacities. Finally, each route is improved by the application of the nearest neighbor heuristic. The results of the experiment indicate that the proposed heuristic is better than the nearest neighbor heuristic for VRP. Moreover, the proposed algorithm can easily be used to generate initial solutions for a wide variety of VRP algorithms.
Article Preview


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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing