New mathematical models of the generalized vehicle routing problem and extensions |
| |
Authors: | Petric? C. Pop Imdat KaraAndrei Horvat Marc |
| |
Affiliation: | a North University of Baia Mare, Department of Mathematics and Computer Science, Baia Mare, Romania b Baskent University, Department of Industrial Engineering, Ankara, Turkey |
| |
Abstract: | The generalized vehicle routing problem (GVRP) is an extension of the vehicle routing problem (VRP) and was introduced by Ghiani and Improta [1]. The GVRP is the problem of designing optimal delivery or collection routes from a given depot to a number of predefined, mutually exclusive and exhaustive node-sets (clusters) which includes exactly one node from each cluster, subject to capacity restrictions. The aim of this paper is to provide two new models of the GVRP based on integer programming. The first model, called the node formulation is similar to the Kara-Bekta? formulation [2], but produces a stronger lower bound. The second one, called the flow formulation, is completely new. We show as well that under specific circumstances the proposed models of the GVRP reduces to the well known routing problems. Finally, the GVRP is extended for the case in which the vertices of any cluster of each tour are contiguous. This case is defined as the clustered generalized vehicle routing problem and both of the proposed formulations of GVRP are adapted to clustered case. |
| |
Keywords: | Network design Vehicle routing problem Generalized vehicle routing problem Generalized traveling salesman problem Integer programming |
本文献已被 ScienceDirect 等数据库收录! |
|