Routing with Reloads

Oertel, Peter (2000) Routing with Reloads. PhD thesis.

Abstract

We examine routing problems with reloads, how they can be modeled, their properties and how they can be solved. We propose a simple model, the Pickup and Delivery Problem with Reloads (RPDP), that captures the process of reloading and can be extended for real world applications. We present results that show that the RPDP is solvable in polynomial time if the number of requests is bounded by a constant. Additionally, we examine a special case of the RPDP, the k-Star Hub Problem. This problem is solvable efficiently by network flow approaches if no more than two hubs are available. Otherwise, it is NP-complete. In the second part of this thesis, additional constraints are incorporated into the model and a tabu search heuristic for this problem is presented. The heuristic has been implemented and tested on several benchmarking instances, both artificial and a real-world application. In the appendix, we discuss the application of column generation for a reload problem.


Actions:
Download: [img] Postscript - Accepted Version
Download (652Kb) | Preview
Download: [img] PDF - Accepted Version
Download (529Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2001-423
Depositing User: Peter Oertel
Date Deposited: 28 Oct 2001 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/423