Skip navigation
Please use this identifier to cite or link to this item:

acessibilidade

http://hdl.handle.net/123456789/584
wcag
Title: Combined route capacity and route length models for unit demand vehicle routing problems
Authors: Godinho, Teresa
Gouveia, Luís
Magnanti, Thomas L.
Keywords: Vehicle routing problem
Hop-indexed network flow models
Travelling salesman problem
Issue Date: May-2008
Publisher: Elsevier
Citation: Godinho, M. T., Gouveia, L., & Magnanti, T. L. (2008). Combined route capacity and route length models for unit demand vehicle routing problems. Discrete Optimization, 5(2), 350-372.
Abstract: Routing Problem (CVRP): (a) capacitated models guaranteeing that the number of commodities (paths) traversing any given arc does not exceed a specified capacity; and (b) hop-constrained models guaranteeing that any route length (number of nodes) does not exceed a given value. The latter might, in turn, be divided into two classes: (b1) those restricting the length of the path from the depot to any node k, and (b2) those restricting the length of the circuit passing through any node k. Our results indicate that formulations based upon circuit lengths (b2) lead to models with a linear programming relaxation that is tighter than the linear programming relaxation of models based upon path lengths (b1), and that combining features from capacitated models with those of circuit lengths can lead to formulations for the CVRP with a tight linear programming bound. Computational results on a small number of problem instances with up to 41 nodes and 440 edges show that the combined model with capacities and circuit lengths produce average gaps of less than one percent. We also briefly examine the asymmetric travelling salesman problem (ATSP), showing the potential use of the ideas developed for the vehicle routing problem to derive models for the ATSP with a linear programming relaxation bound that is tighter than the linear programming relaxation bound of the standard Dantzig, Fulkerson and Johnson [G. Dantzig, D. Fulkerson, D. Johnson, Solution of large-scale travelling salesman problem, Operations Research 2 (1954) 393–410] formulation.
URI: https://repositorio.ipbeja.pt/handle/123456789/584
ISSN: 1572-5286
Publisher version: http://dx.doi.org/10.1016/j.disopt.2007.05.001
Appears in Collections:D-MCF - Artigos em revistas com peer review

Files in This Item:
There are no files associated with this item.


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Currículo DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.