Mathematical Problems in Engineering
Volume 2012 (2012), Article ID 182584, 12 pages
Research Article

Solving the Tractor and Semi-Trailer Routing Problem Based on a Heuristic Approach

1School of Transportation Science and Engineering, BeiHang University, No. 37 Xueyuan Road, Haidian District, Beijing 100191, China
2School of Economics and Management, BeiHang University, No. 37 Xueyuan Road, Haidian District, Beijing 100191, China

Received 27 February 2012; Accepted 27 May 2012

Academic Editor: Jianming Shi

Copyright © 2012 Hongqi Li et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


We study the tractor and semi-trailer routing problem (TSRP), a variant of the vehicle routing problem (VRP). In the TSRP model for this paper, vehicles are dispatched on a trailer-flow network where there is only one main depot, and all tractors originate and terminate in the main depot. Two types of decisions are involved: the number of tractors and the route of each tractor. Heuristic algorithms have seen widespread application to various extensions of the VRP. However, this approach has not been applied to the TSRP. We propose a heuristic algorithm to solve the TSRP. The proposed heuristic algorithm first constructs the initial route set by the limitation of a driver’s on-duty time. The candidate routes in the initial set are then filtered by a two-phase approach. The computational study shows that our algorithm is feasible for the TSRP. Moreover, the algorithm takes relatively little time to obtain satisfactory solutions. The results suggest that our heuristic algorithm is competitive in solving the TSRP.