Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows

Please always quote using this URN: urn:nbn:de:0297-zib-6484
  • Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\% from optimum on state-of-the-art personal computers.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Sven Krumke, Jörg Rambau, Luis Miguel Torres
Document Type:ZIB-Report
Tag:ADAC; branch and bound; column generation; pricing; real world data; real-time; soft time windows; vehicle dispatching
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics
Date of first Publication:2001/09/25
Series (Serial Number):ZIB-Report (01-22)
Published in:Appeared in: Algorithms - ESA 2002. Proceedings of the 10th European Symposium on Algorithms, Rome, Italy, September 17-21, 2002. R. Möhring et al. (eds.) Berlin: Springer 2002. LNCS 2461, pp. 637-648