An Incremental Online Heuristic For Evaluating The Feasibility Of The M-VRPTWAR

Christian Tummel, Christian Franzen, Eckart Hauck and Sabina Jeschke ()
Additional contact information
Sabina Jeschke: RWTH Aachen University, IMA/ZLW

A chapter in Automation, Communication and Cybernetics in Science and Engineering 2011/2012, 2013, pp 753-765 from Springer

Abstract: Abstract In this paper, a heuristic approach for evaluating the feasibility of an instance of the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Assignment Restrictions (m-VRPTWAR) is presented. The heuristic approach tries to find a feasible solution by solving two sub-problems of the m-VRPTWAR: a 3-Dimensional Variable-sized Bin-Packing problem (3DVSBPP) and a Traveling Salesman Problem with Time Windows (TSPTW). In order to address the first problem, an online algorithm is presented. This algorithm expects shipments to be inserted in an online fashion and assigns them to freight routes by first-fit. Repacking already assigned shipments is permitted. The TSPTW part of the problem is addressed by a 2-phase heuristic that is based on algorithms presented in Savelsbergh (1985) and Ascheuer (1996). If there is no feasible solution for a new shipment, this shipment will be rejected. The heuristic approach is evaluated by solving several large-scale scenarios and monitoring the rejection rate of the algorithm.

Keywords: Time Window; Feasible Solution; Travelling Salesman Problem; Travel Salesman Problem; Online Algorithm (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-33389-7_55

Ordering information: This item can be ordered from
http://www.springer.com/9783642333897

DOI: 10.1007/978-3-642-33389-7_55

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().