טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentEliahu Troupiansky
SubjectThe Open Vehicle Routing Problem with Heterogeneous Fleet -
A Heuristic Approach
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Penn Michal
Full Thesis textFull thesis text - English Version


Abstract

Given a directed graph with a depot vertex and demand vertices the VRP (Vehicle Routing Problem) is aimed at minimizing the number of capacitated vehicles needed to supply the required demand and the total routes length. The problem is known to be NP-hard and most of the research effort is targeted at various heuristic methods for solving it.

In the classic problem, the vehicles are required to return to the depot at the end of the trip. If the vehicles are not required to return to the depot, then the problem is termed the Open VRP (OVRP). If, in addition, the capacities and the costs of the vehicles vary, then the problem is denoted as Heterogeneous OVRP.

In this work we focus on the Heterogeneous OVRP and provide a greedy heuristic for solving the problem. Our greedy algorithm consists of two stages - construction of an initial feasible solution and post-optimization. In the construction stage, a feasible solution is gradually constructed; at each step either a customer is added to an existing route of a single vehicle or a new route is established. At the post-optimization stage we use 2-opt to improve the initial solution.

We compare our heuristic to some known algorithms for the homogeneous case and to a Cross-Entropy (CE) procedure in the general heterogeneous case. Our results show that our greedy heuristics out performs CE.