Routing Algorithms with Range Restriction in Sparse Supply Networks. Issue 2 (June 2013)

• Record Type: Journal Article
• Authors: Kämpke, Thomas
• Is Part Of: Journal of algorithms & computational technology. Volume 7:Issue 2(2013)
• Page Start: 145
• Page End: 171
• Publication Date: 2013-06
• Subjects: Hierarchical Planning -- Geometric search -- Shortest paths -- Multi-criteria optimization -- Pareto-optimality; Computer algorithms -- Periodicals; Numerical calculations -- Periodicals; Computer algorithms; Numerical calculations; Periodicals; 518.1
• DOI: 10.1260/1748-3018.7.2.145
• Languages: English
• ISSNs: 1748-3018

Abstract

Shortest paths are computed for vehicles with comparatively small maximum range so that they must refuel, recharge or change batteries along a single trip in a road network. Heuristic solutions are given as well as exact algorithms. For sparse networks of service stations, shortest paths within these subnetworks serve as core paths. Extensions from the origin and towards the destination then yield overall shortest paths. Preprocessing shortest paths in sparse subnetworks allows computational speed-up. Parametric problem versions are dealt with by simultaneously minimizing overall path length and minimizing the length of the longest arc in use.