A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

0.00 Avg rating0 Votes
Article ID: iaor20083091
Country: Netherlands
Volume: 38
Issue: 4
Start Page Number: 555
End Page Number: 580
Publication Date: Aug 2007
Journal: Journal of Global Optimization
Authors: , ,
Keywords: heuristics: genetic algorithms
Abstract:

In this paper, the Vehicle Routing Problem (VRP) is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results.

Reviews

Required fields are marked *. Your email address will not be published.