Second International Workshop on Model Based Metaheuristics , 2008-06-16

Title : ( An ILP Improvement Procedure for the Open Vehicle Routing Problem )

Authors: Majid Salari , Paolo Toth , Andrea Tramontani ,

Citation: BibTeX | EndNote

Abstract

We address the Open Vehicle Routing Problem (OVRP), a variant of the \classical" Vehicle Routing Problem (VRP) in which the vehicles are not required to return to the depot after completing their service. We present a heuristic improvement procedure for OVRP based on Integer Linear Programming (ILP) techniques. Given an initial solution to be possibly improved, the method follows a destruct-and- repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in the attempt of finding a new improved solution. The overall procedure can be considered as a general framework which could be extended to cover other variants of Vehicle Routing Problems. We report computational results on benchmark instances from the literature. In several cases, the proposed algorithm is able to find the new best-known solution for the considered problem.

Keywords

, integer linear programming, local search, heuristics, open vehicle routing problem
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1022380,
author = {Salari, Majid and Paolo Toth and Andrea Tramontani},
title = {An ILP Improvement Procedure for the Open Vehicle Routing Problem},
booktitle = {Second International Workshop on Model Based Metaheuristics},
year = {2008},
location = {Bertinoro, ITALY},
keywords = {integer linear programming; local search; heuristics; open vehicle routing problem},
}

[Download]

%0 Conference Proceedings
%T An ILP Improvement Procedure for the Open Vehicle Routing Problem
%A Salari, Majid
%A Paolo Toth
%A Andrea Tramontani
%J Second International Workshop on Model Based Metaheuristics
%D 2008

[Download]