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

Abdesslem Layeb
Additional contact information
Abdesslem Layeb: Department of Information and Applications, University of Constantine II, Constantine, Algeria

International Journal of Operations Research and Information Systems (IJORIS), 2015, vol. 6, issue 1, 78-90

Abstract: 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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 18/ijoris.2015010106 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:joris0:v:6:y:2015:i:1:p:78-90

Access Statistics for this article

International Journal of Operations Research and Information Systems (IJORIS) is currently edited by John Wang

More articles in International Journal of Operations Research and Information Systems (IJORIS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().