@misc{SchwanStrehler, author = {Schwan, Christian and Strehler, Martin}, title = {Energy-efficient Routing of Hybrid Vehicles}, series = {arXiv.org}, journal = {arXiv.org}, pages = {11}, abstract = {We consider a constrained shortest path problem with two resources. These two resources can be converted into each other in a particular manner. Our practical application is the energy optimal routing of hybrid vehicles. Due to the possibility of converting fuel into electric energy this setting adds new characteristics and new combinatorial possibilities to the common constrained shortest path problem (CSP). We formulate the resulting problem as a generalization of CSP. We show that optimal paths in this model may contain cycles and we state conditions to prevent them. The main contribution is a polynomial-time approximation scheme and a simpler approximation algorithm for computing energy-optimal paths in graphs.}, language = {en} } @inproceedings{SchefflerStrehler, author = {Scheffler, Robert and Strehler, Martin}, title = {Optimizing Traffic Signal Timings for Mega Events}, series = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), ATMOS'16, August 25, 2016, Aarhus, Denmark}, booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), ATMOS'16, August 25, 2016, Aarhus, Denmark}, editor = {Goerigk, Marc and Werneck, Renato}, publisher = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-021-7}, doi = {10.4230/OASIcs.ATMOS.2016.8}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-66724}, pages = {8,1 -- 8,16}, language = {en} } @inproceedings{SchadeStrehler, author = {Schade, Stanley and Strehler, Martin}, title = {The Maximum Flow Problem for Oriented Flows}, series = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, editor = {Goerigk, Marc and Werneck, Renato}, publisher = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-021-7}, doi = {10.4230/OASIcs.ATMOS.2016.7}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-65318}, pages = {1 -- 13}, abstract = {In several applications of network flows, additional constraints have to be considered. In this paper, we study flows, where the flow particles have an orientation. For example, cargo containers with doors only on one side and train coaches with 1st and 2nd class compartments have such an orientation. If the end position has a mandatory orientation, not every path from source to sink is feasible for routing or additional transposition maneuvers have to be made. As a result, a source-sink path may visit a certain vertex several times. We describe structural properties of optimal solutions, determine the computational complexity, and present an approach for approximating such flows.}, language = {en} }