Routing and Networks

9:00am – 2:30pm
January 15, 2014

Sky Lounge, 12th Floor
Faculty of Business, Economics, and Statistics
University of Vienna
Oskar-Morgenstern-Platz 1
1090 Vienna, Austria

Bernard Fortz, Université Libre de Bruxelles
Daniele Vigo, University of Bologna

Workshop Program:

09:00 – 09:10 Welcome

Keynote Talk I
09:10 – 09:55 Bernard Fortz, Université Libre de Bruxelles Time-dependent combined network design and routing optimization (Abstract)
In today’s communication networks, distributed control functions such as routing inherit design driven by processing capacity and memory consumption. Henceforth, the routing protocol decision process (distributed and online) remains still decoupled from the routing optimization process (centralized and offline). Distributed optimization does not take into account the distributed nature of the online routing decision making process because distributed optimization is not decomposed along the same dimensions as the routing decision making process. The challenge becomes thus how to modify the routing decision process to include optimization objectives and how to make the optimization problem aware of the distributed nature of the online routing decision process under dynamic conditions. As a first evolution in that direction, we propose a new combined optimization model that integrates network design decisions and routing decisions, with time-dependent demands. As part of our main contribution, the proposed model keeps in sight the need for a distributed routing function, through the use of scalable routing tables. We also put our work in the perspective of a fully distributed, decomposed optimization setting.
(joint work with Dimitri Papadimitriou, Alcatel-Lucent)

09:55 – 10:10 Coffee Break

Invited Talks:
10:10 – 10:40 Matthias Prandtstetter, Austrian Institute of Technology: Intermodal E-Mobility Routing incorporating (E-)Car-Sharing (Abstract)
Within this work, we present a flexible and expandable routing framework capable of finding multi-modal and inter-modal energy-efficient routes incorporating, among others, transportation modes such as public transport, electric vehicles, car-sharing, bike-sharing and walking. In contrast to conventional trip planning services, the proposed framework can evaluate routes not only with respect to travel distance or travel time but also with respect to energy used. In addition, range limitation by electric vehicles is incorporated into the routing request such that range-safety can be provided.
(joint work with Markus Straub and Jakob Puchinger)
10:40 – 11:10 Mario Ruthmair, Vienna University of Technology: Modeling and Solving the One-to-One Multi-Commodity Pickup and Delivery Traveling Salesman Problem (Abstract)
We address the one-to-one multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) introduced by Hernandez-Perez and Salazar-Gonzalez (2009). The problem arises in several transportation and logistics applications. We show that the m-PDTSP is equivalent to a different problem variant, the many-to-many one-commodity pickup and delivery traveling salesman problem (1-PDTSP), with additional precedence constraints. The advantage of using this relation to model the m-PDTSP is that we are able to model the capacity constraints just by considering a single commodity. The precedence relations are ensured separately by adding inequalities for the sequential ordering polytope (SOP), see Balas et al. (1995). Furthermore, we present alternative ways to model the capacity constraints based on load-dependent layered graphs which are beneficial for tight capacities in terms of LP bounds. In particular we consider a formulation based on a 3-dimensional layered graph that combines time and load together and even achieves tighter LP bounds, at the cost of a large model size. Especially for tightly capacitated instances with a large number of commodities our branch-and-cut algorithms outperform the existing approaches. Additionally, we consider the uncapacitated m-PDTSP which is equivalent to the TSP with precedence constraints (or sequential ordering problem). Here, an adapted variant of our branch-and-cut algorithm is able to solve to optimality several open instances from the TSPLIB.
(joint work with Luis Gouveia)
11:10 – 11:40 Sophie N. Parragh, Vienna University of Economics and Business: Solving the bi-objective team orienteering problem by branch-and-price (Abstract)
This research is motivated by recent advances in branch-and-bound algorithms for multi-objective combinatorial optimization problems and successful implementations of column generation and branch-and-price based methods for single-objective vehicle routing problems. We propose a multi-objective branch-and-price algorithm and apply it to the bi-objective team orienteering problem with time windows (BO-TOPTW). In the BO-TOPTW, a set of locations is given. Each location is associated with a profit, a service time, and a time window. The number of routes that can be used to visit the different locations is fixed. The first objective corresponds to maximizing the total collected profit and the second to minimizing total routing costs. The aim is to generate the complete set of Pareto optimal solutions. The BO-TOPTW is formulated as a set-packing type problem whose linear relaxation, embedded into Aneja-Nair’s algorithm, can be solved by column generation. Since we are interested in a framework that is as independent from the problem studied as possible, our focus lies on the exploration of efficient pruning and branching schemes. We analyze the impact of these two ingredients on the performance of the whole method and we show the advantages and disadvantages of our framework in comparison to an epsilon-constraint based scheme.
(joint work with Fabien Tricoire)
11:40 – 12:10 Karl Dörner, University Linz: The school bus routing and scheduling problem with transfers (Abstract)
In this talk we present the school bus routing and scheduling problem with transfers, which is an important and interesting problem in the field of non periodic public transportation services. It deals with the planning of the transportation of pupils from home to their school before it starts with consideration that pupils may change buses. Allowing for transfers has multiple different consequences. On the one hand, costs can possibly be reduced significantly. On the other hand transfers clearly have an impact on the service level, i.e., transfers lower the service level, but may also reduce ride times. We develop a heuristic solution framework to solve this problem and use two additional solution techniques that do not consider transfers and analyze the results of the three methods. The main objective of our approach is the minimization of costs. The implications on the service level of the pupils, like time loss and number of transfers, are analyzed. The computational experiments show that the costs can be reduced significantly and the average and maximum ride times are comparable to solutions without transfers.
(joint work with Michael Bögl and Sophie N. Parragh)

12:10 – 13:00 Lunch Break

Keynote Talk II
13:00 – 13:45 Daniele Vigo, University Bologna Practical issues arising in small-package shipping (Abstract)
We address two specific issues arising in the planning of distribution routes for the small-package industry. The first one is related to area-based routing which is frequently employed in these applications to favor driver familiarity for the service. We investigate the impact of time windows in the construction of service areas used to define the daily routes for the drivers. The second characteristic we examine is the possibility of subcontracting unprofitable customers to external providers so that the owned fleet can be reduced and concentrates on the most important areas. We present state-of-the-art heuristic algorithms and the results of their extensive computational testing.

13:45 – 13:50 Oliver Fabel, University of Vienna

Sponsored by:
Faculty of Business, Economics, and Statistics, University of Vienna
Austrian Society of Operations Research
Dynamic Transportation Systems, Austrian Institute of Technology

Organized by:
Markus Leitner, University of Vienna
Ivana Ljubic, University of Vienna
Jakob Puchinger, Austrian Institute of Technology