Lower and upper bounds for location-arc routing problems with vehicle capacity constraints |
| |
Authors: | Seyed Hossein Hashemi Doulabi Abbas Seifi |
| |
Affiliation: | Department of Industrial Engineering, Amirkabir University of Technology, Tehran, Iran; Industrial Engineering and Productivity Research Center, Amirkabir University of Technology, Tehran, Iran |
| |
Abstract: | 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. |
| |
Keywords: | Location-arc routing Arc routing Integrated logistics Mixed integer programming Heuristics |
本文献已被 ScienceDirect 等数据库收录! |