Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

► A location-arc routing problem with capacity constraints is formulated. ► The average cost saving due to changing the location of a central depot is 13.82%. ► The maximum saving from location improvement happens to be 56.54%. ► When the allowable number of locations increases, the marginal saving...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2013-01, Vol.224 (1), p.189-208
Main Authors: Hashemi Doulabi, Seyed Hossein, Seifi, Abbas
Format: Article
Language:English
Subjects:
Applied sciences
Arc routing
Exact sciences and technology
Flows in networks. Combinatorial problems
Heuristic
Heuristics
Integer programming
Integrated logistics
Location analysis
Location-arc routing
Logistics
Mathematical problems
Mathematical programming
Mixed integer programming
Operational research and scientific management
Operational research. Management science
Route optimization
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:► A location-arc routing problem with capacity constraints is formulated. ► The average cost saving due to changing the location of a central depot is 13.82%. ► The maximum saving from location improvement happens to be 56.54%. ► When the allowable number of locations increases, the marginal saving decreases. ► As the vehicle capacity is more limited, the problem becomes more difficult. This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2012.06.015