A Heuristic Algorithm for Multiple Depots Vehicle Routing Problem with Backhauls

Author

Fan, Jianhua ; Wang, Xiufeng ; Chen, Qiushuang

Author_Institution

Tianjin Univ. of Technol., Tianjin

Volume

3

fYear

2007

fDate

24-27 Aug. 2007

Firstpage

421

Lastpage

425

Abstract

An algorithm for multiple depots vehicle routing problem with backhauls is proposed and the goal is to minimize the total traveling cost in reasonable computation time. Firstly borderline customers are determined and the remaining customers are allocated to the nearest depot. Secondly, an effective method is presented to construct the initial routings and insert the borderline customers into the appropriate location. Finally, the initial routings are improved by post-optimization procedure. Some reduction computation strategies are designed to enhance algorithm efficiency. The experiment results indicate that this algorithm can produce encouraging results with less computation time.

Keywords

minimisation; resource allocation; transportation; vehicles; backhauling; borderline customers; customer allocation; heuristic algorithm; initial routings; multiple depots vehicle routing problem; post-optimization procedure; total traveling cost minimization; Algorithm design and analysis; Clustering algorithms; Computational efficiency; Computer science; Costs; Heuristic algorithms; Information technology; Lagrangian functions; Routing; Vehicles;

fLanguage

English

Publisher

ieee

Conference_Titel

Fuzzy Systems and Knowledge Discovery, 2007. FSKD 2007. Fourth International Conference on

Conference_Location

Haikou

Print_ISBN

978-0-7695-2874-8

Type

conf

DOI

10.1109/FSKD.2007.42

Filename

4406273