A Self-Bounding Branch \& Bound procedure for truck routing and scheduling

Authors

  • Csongor Gy. Csehi Budapest University of Technology and Economics
  • Ádám Tóth Nexogen Ltd.
  • Márk Farkas Nexogen Ltd.

DOI:

https://doi.org/10.31449/inf.v43i1.2681

Abstract

In this paper we study a part of a core algorithm of a complex software solution for truck itinerary construction for one of the largest public road transportation companies in the EU. The problem is to construct a cost optimal itinerary, given an initial location with an asset state, the location and other properties of tasks to be performed. Such an itinerary specifies the location and activity of the truck and the driver until the completition of the last routing task. The calculation of possible itineraries is a branch and bound algorithm. The nodes of the search tree have the following arguments: position, time, driver-state and truck-state. For each node we calculate the cumulative cost for the road reaching that state, and a heuristic lower bound for the cost of the remaining road. In each step the procedure expands the next unexpanded node with the best sum for cumulative and heuristical costs.\\ It is hard to give a sharp lower bound if the model contains time windows. To make a sharp heuristic we run the same branch and bound algorithm (from each node) but with simplified data (hypothetical positions and simplified activities: no refuelling, no road costs, etc.). We have reached significant gains in performance and quality compared to the previous approach.

References

bibitem{carter}

M. W. Carter, C. C. Price (2000) {it Operations research: a practical introduction}, Crc Press.

bibitem{chung}

C. S. Chung, J. Flynn, "{O}. Kirca, (2006) A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems. {it European Journal of Operational Research}, 174(1), 1--10.

bibitem{companys}

R. Companys, M. Mateo (2007) Different behaviour of a double branch-and-bound algorithm on Fm| prmu| Cmax and Fm| block| Cmax problems. {it Computers & Operations Research}, 34(4), 938--953.

bibitem{truck}

Cs. Gy. Csehi, M. Farkas (2016) Truck routing and scheduling, Central {it European Journal of Operations Research}, 1--17. doi: 10.1007/s10100-016-0453-8

bibitem{cui}

Y. Cui, Y. Yang, X. Cheng, P. Song (2008) A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem. {it Computers & Operations Research}, 35(4), 1281--1291.

bibitem{floyd}

R. W. Floyd (1962) Algorithm 97: Shortest path, {it Communications of the ACM} 5(6):345

bibitem{hartwig1}

A. Hartwig (1985) Recursive branch and bound. {it Optimization}, 16(2), 219--228.

bibitem{hartwig2}

A. Hartwig, F. Daske, S. Kobe (1984) A recursive branch-and-bound algorithm for the exact ground state of Ising spin-glass models. {it Computer Physics Communications}, 32(2), 133--138.

bibitem{matsuzaki}

R. Matsuzaki, A. Todoroki (2007) Stacking-sequence optimization using fractal branch-and-bound method for unsymmetrical laminates. {it Composite Structures}, 78(4), 537--550.

bibitem{vanhoucke1}

M. Vanhoucke (2002) Optimal due date assignment in project scheduling. {it Vlerick Management School.}

bibitem{vanhoucke2}

M. Vanhoucke (2006) Scheduling an R&D project with quality-dependent time slots. {it International Conference on Computational Science and Its Applications} (pp. 621--630). Springer Berlin Heidelberg.

bibitem{warshall}

S. Warshall (1962) A theorem on Boolean matrices, {it Journal of the ACM} 9(1):11--12

Downloads

Published

2019-03-01

How to Cite

Csehi, C. G., Tóth, Ádám, & Farkas, M. (2019). A Self-Bounding Branch \& Bound procedure for truck routing and scheduling. Informatica, 43(1). https://doi.org/10.31449/inf.v43i1.2681

Issue

Vol. 43 No. 1 (2019)

Section

Middle-European Conference on Applied Theoretical Computer Science (MATCOS-16)

License

I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.

I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.

In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.

I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal.  The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.


Copyright ©  Slovenian Society Informatika