Solving a Real-world Problem of Truck-Trailer Scheduling in Container Transportation by Local Search
Main Article Content
Abstract
Container transportation plays a very important role in global supply chains where companies of different countries exchange goods overseas. Operational costs of transporting containers are extremely high. Hence, optimizing itinerary schedules brings substantial benefits to logistics companies. In this paper, we investigate a realistic container transportation schedule problem in which trucks, trailers, and containers are separate objects located at different terminals, and trucks are planned to take trailers and carry containers between container depots, ports, and customer warehouses. In this context, containers can be 40ft or 20ft, and a trailer can carry one 40ft container or one 20ft container, or two 20ft containers. Moreover, a truck can detach the trailer and leave both the container and trailer at the warehouse if no available forklift. We first propose a mixed-integer linear programming model for describing the problem. Then, we propose a local search algorithm for solving the problem. Experiments on generated data instances show the benefits of the proposed algorithm that about 19.62% on average compared to the previously proposed algorithm. Furthermore, the application of the model leads to rapidity in generating the solution; this task that used to take days is decreased to just one hour.
Keywords
vehicle routing problem, container transportation, drayage operation, local search
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
References
[1] R. Zhang, Y. Yun, I. Moon, Modeling and optimization of a container drayage problem with resource constraints. International Journal of Production Economics, 2011, vol. 133, pp. 351-359. https://doi.org/10.1016/j.ijpe.2010.02.005
[2] R. Zhang, L. Jye-Chyi, D. Wang, Container drayage problem with flexible orders and its near real-time solution strategies. Transportation Research Part E: Logistics and Transportation Review, 2014, vol. 61, pp. 235–251. https://doi.org/10.1016/j.tre.2013.11.009
[3] Fazi, S., Fransoo, J. C., Van Woensel, T., Dong, J. X., A variant of the split vehicle routing problem with simultaneous deliveries and pickups for inland container shipping in dry-port based systems. Transportation Research Part E: Logistics and Transportation Review, 2020, vol. 142. https://doi.org/10.1016/j.tre.2020.102057
[4] J. You, L. Miao, C. Zhang, Z. Xue, A generic model for the local container drayage problem using the emerging truck platooning operation mode. Transportation Research Part B: Methodological, 2020, vol. 133, pp. 181-209. https://doi.org/10.1016/j.trb.2019.12.009
[5] Xue, Z., Lin, H., You, J., Local container drayage problem with truck platooning mode. Transportation Research Part E: Logistics and Transportation Review, 2021, 147:102211. https://doi.org/10.1016/j.tre.2020.102211
[6] M. Drexl, Branch-and-price and heuristic column generation for the generalized truck-and-trailer routing problem. Revista de Metodos Cuantitativos para la Economia y la Empresa, 2011, vol. 12, pp. 5-38.
[7] Song, Y., Zhang, J., Liang, Z., Ye, C., An exact algorithm for the container drayage problem under a separation mode. Transportation Research Part E: Logistics and Transportation Review, 2017, vol. 106. https://doi.org/10.1016/j.tre.2017.07.010
[8] J. Funke, H. Kopfer, A model for a multi-size inland container transportation problem. Transportation Research Part E: Logistics and Transportation Review, 2016, vol. 89, pp. 70-85. https://doi.org/10.1016/j.tre.2016.02.010
[9] V. S. Nguyen, Q. D. Pham, A new variant of truck scheduling for transporting container problem, in Proc. SoICT, Vietnam, 2019, pp. 139-146.
[10] O. Braysy, M. Gendreau, Vehicle routing problem with time windows, Part I: Route construction and local search algorithms, Transportation Science, 2015, vol. 39(1), pp. 104-118. https://doi.org/10.1287/trsc.1030.0056
[11] C. Groër, B. Golden, E. Wasil, A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation, 2010, vol. 2, pp. 79-101. https://doi.org/10.1007/s12532-010-0013-5
[12] Q. D. Pham, L. K. T. Nguyen, V. D. Pham, and Q. T. Bui, A constraint-based local search for offline and online general vehicle routing. International Journal on Artificial Intelligence Tools, 2016, vol. 26. https://doi.org/10.1142/S021821301750004X
[2] R. Zhang, L. Jye-Chyi, D. Wang, Container drayage problem with flexible orders and its near real-time solution strategies. Transportation Research Part E: Logistics and Transportation Review, 2014, vol. 61, pp. 235–251. https://doi.org/10.1016/j.tre.2013.11.009
[3] Fazi, S., Fransoo, J. C., Van Woensel, T., Dong, J. X., A variant of the split vehicle routing problem with simultaneous deliveries and pickups for inland container shipping in dry-port based systems. Transportation Research Part E: Logistics and Transportation Review, 2020, vol. 142. https://doi.org/10.1016/j.tre.2020.102057
[4] J. You, L. Miao, C. Zhang, Z. Xue, A generic model for the local container drayage problem using the emerging truck platooning operation mode. Transportation Research Part B: Methodological, 2020, vol. 133, pp. 181-209. https://doi.org/10.1016/j.trb.2019.12.009
[5] Xue, Z., Lin, H., You, J., Local container drayage problem with truck platooning mode. Transportation Research Part E: Logistics and Transportation Review, 2021, 147:102211. https://doi.org/10.1016/j.tre.2020.102211
[6] M. Drexl, Branch-and-price and heuristic column generation for the generalized truck-and-trailer routing problem. Revista de Metodos Cuantitativos para la Economia y la Empresa, 2011, vol. 12, pp. 5-38.
[7] Song, Y., Zhang, J., Liang, Z., Ye, C., An exact algorithm for the container drayage problem under a separation mode. Transportation Research Part E: Logistics and Transportation Review, 2017, vol. 106. https://doi.org/10.1016/j.tre.2017.07.010
[8] J. Funke, H. Kopfer, A model for a multi-size inland container transportation problem. Transportation Research Part E: Logistics and Transportation Review, 2016, vol. 89, pp. 70-85. https://doi.org/10.1016/j.tre.2016.02.010
[9] V. S. Nguyen, Q. D. Pham, A new variant of truck scheduling for transporting container problem, in Proc. SoICT, Vietnam, 2019, pp. 139-146.
[10] O. Braysy, M. Gendreau, Vehicle routing problem with time windows, Part I: Route construction and local search algorithms, Transportation Science, 2015, vol. 39(1), pp. 104-118. https://doi.org/10.1287/trsc.1030.0056
[11] C. Groër, B. Golden, E. Wasil, A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation, 2010, vol. 2, pp. 79-101. https://doi.org/10.1007/s12532-010-0013-5
[12] Q. D. Pham, L. K. T. Nguyen, V. D. Pham, and Q. T. Bui, A constraint-based local search for offline and online general vehicle routing. International Journal on Artificial Intelligence Tools, 2016, vol. 26. https://doi.org/10.1142/S021821301750004X