A column generation approach for the vehicle routing problem in a hybrid hub-and-spoke network


Jiyoung Choi, Chungmok Lee, and Sungsoo Park



This paper addresses a vehicle routing problem which decides both the transportation routes and the number and types of vehicles to be deployed to minimize the sum of costs to transport all quantities in a hybrid hub-and-spoke network which allows direct transportation between spokes. We propose an extended formulation of the routing problem which yields a strong LP relaxation bound by introducing a set of feasible direct route patterns and the Dantzig-Wolfe decomposition approach. We develop an algorithm which incorporates column generation procedure at the root node and repeats iteratively a variable fixing and column generation procedure at the non-root nodes until an integral solution is found. For computational study, the proposed algorithm was applied to real transportation networks of Turkey and Korea Post. The results show that our algorithm can find near optimal solutions very efficiently.


Keywords: hybrid hub-and-spoke, vehicle routing problem, decomposition, column generation, variable fixing


Contact Address :

Sungsoo Park, Professor,

Department of Industrial and Systems Engineering

Korea Advanced Institute of Science and Technology (KAIST)

291 Daehak-ro, Yuseong-gu, Daejeon, 305-701, Republic of Korea

PHONE : +82-42-350-3121

FAX : +82-42-350-3110

E-mail : sspark@kaist.ac.kr