Title: An exact algorithm for the three-dimensional loading capacitated vehicle routing problem

Authors: Jidong Ren; Yajie Tian; Tetsuo Sawaragi

Addresses: Graduate School of Engineering, Kyoto University, Sakyo-ku, Kyoto 606-8501, Japan. ' Graduate School of Engineering, Kyoto University, Sakyo-ku, Kyoto 606-8501, Japan. ' Graduate School of Engineering, Kyoto University, Sakyo-ku, Kyoto 606-8501, Japan

Abstract: The three-dimensional loading capacitated vehicle routing problem is a strong NP-hard problem. Most existing algorithms for the problem are heuristic or meta-heuristic algorithms. In this paper, an exact algorithm is proposed for the problem. For solving the loading sub-problem, we use an effective method to generate possible points for loading items, which greatly reduce the search scope. Then we proposed an exact algorithm which iteratively calls a branch-and-bound algorithm based on set partition. The validity of the proposed algorithm is examined by comparing the present results with those of published algorithms using the same data.

Keywords: vehicle routing problem; set partition; container loading problem; CLP; branch-and-bound algorithm; heuristics; 3D loading capacitated VRP.

DOI: 10.1504/IJBPSCM.2012.050391

International Journal of Business Performance and Supply Chain Modelling, 2012 Vol.4 No.3/4, pp.317 - 332

Available online: 16 Nov 2012 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article