Abstracts

Plenary talk: Choice-based Optimization in City Logistics

• Virginie Lurkin
• University of Lausanne
• Over the last decade, the ever-accelerating trends of e-commerce and urbanization led the logistics community to define rich facility locations and routing problems, embedding new attributes to better feature real-world environments. Although the objective of smooth and seamless flow of goods in urban areas remains over the years, more sophisticated formulations (in terms of objectives and/or constraints) have been introduced to capture the complexity of city logistics problems more accurately. Well-known examples are the inclusion of environmental concerns or uncertain traffic conditions within the problem definition.
  While all these problems require demand data as input, the logistics community has mainly focused on the operational objective and constraints of the supplier, ignoring the critical role of the behavior of the consumers. Aggregation or simplifying assumptions are made on the demand side. In this talk, I will discuss how it is possible to embed customers behaviors within city logistics optimization problems. While doing so allows to better reflect the supply-demand interactions within the system, it also leads to hard optimization problems, for which suited solutions methods need to be designed.

Plenary talk: A Linear Programming Approach to Approximate Dynamic Programming

• Christiane Barz
• University of Zurich
• Traditional methods to find solutions to the Bellman equations include value iteration, policy iteration and linear programming. All of those methods suffer from the curse in dimensionality: if realistic, multi-dimensional states are modelled, the size of the state space increases exponentially in the dimension of the states making an exact solution difficult, if not impossible. The main idea of approximate dynamic programming is to assume a parameterized structure of the value function. As a consequence, only a handful of parameters must be determined (and not one value for each state).
  Researchers investigate both simulation based approaches as well as linear programming based approaches to approximate dynamic programming. In this talk, I explain the main idea of the linear programming based approach and provide examples of past and current research in this area.

Industrial plenary talk: SWISS: Optimizing Airline Tail Assignments and Making Air Travel More Sustainable

• Kadir Göçer
• Swiss International Air Lines
• The economic impact of the COVID-19 pandemic has been catastrophic for airlines, and after that, rapidly rising fuel prices are the next financial hurdle. In addition, the International Civil Aviation Organization (ICAO) has set some hard CO₂ commitments. To deal with these financial and political issues, Swiss International Airlines (SWISS) has entered into a strategic partnership with Google Cloud to develop a data-driven optimization framework for flight operations. Called Operations Decision Support Suite (OPSD), this collaboration aims to build a shared data repository containing crew, passenger, rotation and maintenance information to optimize SWISS’s overall flight operations with an automated decision support system.
  As a first step and use case, we developed together with Google’s Operations Research team a Tail Assignment Solver that minimizes total operating costs, including fuel as one of the most important cost elements, thus reducing CO₂ emissions. After using Tail Solver to optimize our fleet schedule, we were able to save 1 million Swiss francs and reduce CO₂ emissions by 1800 tons in the first 14 weeks (2021).

Contributed talks

Choice-Based Routing in Attended Home Delivery

• Dorsa Abdolhamidi, Virginie Lurkin
• University of Bern
• While e-commerce has been long on the rise, the closure of shops and restaurants during Covid lockdowns has further bumped up the requests for home deliveries in limited urban spaces, worsening the issues related to urban logistics. Customers expect to be delivered at home at a convenient time and fast and reliable way. To meet customers’ expectations, many e-shops allow consumers to select their favorite delivery time windows from a menu of time-slots. Enabling consumers to select their preferred delivery time increases customers’ satisfaction but might cause higher delivery costs for the online retailer. In this study, we explore a static vehicle routing in which the customers’ preferences regarding time windows are explicitly taken into account. More specifically, customers’ choice is captured with a multinomial logit model. Using simulation, we present a mixed-integer linear programming formulation. The goal is to minimize the retailer routing costs while maximizing customers’ utility functions. We demonstrate the effectiveness of the formulation on several instances solved exactly.

Policy-Focused Fleet Size Minimization of Autonomous Robots in a Multimodal Last-Mile Delivery Transportation Context

• Mikele Gajda, Nils Boysen, Olivier Gallay
• University of Lausanne
• Taking inspiration from modern last-mile delivery prototypes involving the usage of autonomous delivery robots (ADRs) in combination with transportation vans, we propose a study that assesses the impact that different return policies have on the robots fleet size. In the considered framework, ADRs that operate at pedestrian pace on sidewalks are dispatched from vans at appropriate locations (i.e., drop-off points). After successfully performing a delivery job, ADRs return to a depot where batteries can be swapped and they can be utilized by another van for a further delivery. We position our study following the logic of appropriately selecting the return depot, thus providing a comprehensive overview of some of the most common return policies that might be used to minimize the overall robot fleet size. Starting from pre-computed van routes and ADR launch schedules, we consider an extensive set of instances involving various collections of delivery jobs performed by different vans in given areas of interest that differ in their geographical customer and depot distributions. This set-up allows us to build a method for reassigning used ADRs to new delivery jobs and compare alternative return policies to determine the resulting reusability rate. Following this analysis and associated computational experiments, we highlight the impact of each of the considered return policies. In particular, we propose adapted optimization algorithms for three possible ADR return policies: dedicated-station policy; closest-station policy; and most-suitable-station policy. The results demonstrate the necessity, in a preliminary stage, of carefully designing the best possible return policy in order to complete a given delivery plan with as few ADRs as possible.

A Novel Continuous-Time Mixed-Integer Linear Programming Model for the Multi-Mode Resource-Constrained Project Scheduling Problem

• Nicklas Klein
• University of Bern
• Project scheduling has become a vital component of many businesses across different industries. In many real-world projects, the durations and resource requirements of activities are not fixed, but there may be tradeoffs between higher resource requirements and smaller processing times. These tradeoffs can be represented through multiple execution modes of the activities, which is considered in the multi-mode resource-constrained project scheduling problem (MRCPSP). In the MRCPSP, a set of precedence-related project activities is given, which each have different possible execution modes. Depending on the mode, the activities require time and scarce resources to process. Sought are the start times and execution modes of the activities such that the project completion time (makespan) is minimized.
  We present a novel continuous-time mixed-integer linear programming (MILP) model for the MRCPSP, which is based on activity order. Specifically, we use mode-selection variables, and two kinds of order variables to determine an optimal solution. In contrast to the current state-of-the-art MILP models from the literature, the new model has a polynomial number of variables and constraints. A computational comparison to MILP models from the literature shows promising results, indicating that the novel model outperforms the current state-of-the-art models on benchmark instances with long activity durations.

Scheduling with Time-Dependent Processing Time Functions of V-Shaped Linear Pieces

• Helmut A. Sedding
• ZHAW
• Scheduling is classically centered around jobs with constant processing times. This allows for universal methods of a simple structure, like Smith’s rule, proven by job interchange arguments. Certain applications, however, entail variable processing times, depending on the job’s start time. Then, interchanging jobs implies changing start times for successive jobs, which escalates the computational complexity. To plan car assembly on a moving conveyor line, we are concerned with time-dependent processing time functions that are V-shaped and piecewise-linear. We present complexity results and draw relations to classic scheduling problems.

Distributed Asynchronous Column Generation

• Saverio Basso, Alberto Ceselli
• SUPSI
• In this work, we study how to find good dual bounds for generic mixed integer mathematical programs (MIPs) as fast as possible, when facing large scale problems and when clusters of multi-core machines are available. In particular, we consider column generation algorithms to solve the extended formulations obtained through Dantzig-Wolfe decompositions for MIPs and we propose a new algorithm that can fully exploit distributed computing resources to obtain massive parallelism.
  Our efforts focus on relaxing the synchronized nature of the classical methods by decoupling the control flow of the master problem and the other components. This allows pricing algorithms to work concurrently on possibly different sets of dual variables, as the master problem can update, in an asynchronous fashion, dual information as soon as any column of reduced cost is found. We exploit simple data structures and efficient synchronization to ensure the same optimality guarantees of the classical methods.
  We consider large scale datasets of three problems from the combinatorial optimization literature for benchmark, comparing our distributed algorithms to both standard and asynchronous single machine parallelization of column generation and state-of-the-art solvers. Our distributed algorithms result capable of exploiting all the available resources, resulting faster than earlier attempts from the literature, also when run on a single physical machine. Overall, when facing large scale instances, they perform one order of magnitude faster than general purpose solvers.

On k-Community Structures in Special Graph Classes

• Narmina Baghirova, Clément Dallard, Bernard Ries, David Schindl
• University of Fribourg
• A k-community structure in an undirected graph is a partition of its vertex set into k sets (called communities), each of size at least two, such that every vertex of the graph has proportionally at least as many neighbours in its own community as in any other community. In this paper, we show that for any fixed k ≥ 2, a tree T admits a k-community structure if and only if T contains a matching of size k. Furthermore, if such a k-community exists, it can be found in polynomial time. This generalises a result from another paper, where it was shown that all trees except stars admit a 2-community and it can be found in polynomial time. We also show that if communities are allowed to have size one, then every tree with at least k vertices admits a k-community structure that can be found in polynomial time, for every fixed integer k ≥ 2.
  We then consider threshold graphs, and after pointing out that each of them admits a trivial 2-community structure with one community containing a unique vertex, we exhibit a subfamily of threshold graphs that always admit a 2-community structure can be found in linear time. Furthermore, we introduce a new infinite family of graphs that do not admit any 2-community structure (even if communities are allowed to have size one). Such a family was presented in another paper by Bazgan et. al., but its graphs all contained an even number of vertices. The graphs in our new family may contain an even or odd number of vertices.

OR and Citizens: An Overview and Case Study Example

• Alice H. Aubert, Judit Lienert
• Eawag
• Operations Research (OR) is often participatory, engaging stakeholders. Citizen participation is receiving growing interest in various fields and political spheres. We systematically reviewed the OR literature to characterize the status of “citizens” in OR processes. We found that (1) OR traditionally postulates that the research is done to improve the systems we live in, i.e. improve citizens’ life, (2) some fields such as community OR include citizens in the OR processes, and (3) some OR scientists emphasize their civic engagement while conducting their research. We identified at least eight research opportunities for OR. In our talk, we will present the results of this review and exemplify some research opportunities with our work. In a case study in the Paris region, we elicited online the trade-off preferences from 655 citizens in a decision directly affecting them: the future of their wastewater infrastructure. This work contributed to empirical testing of digital tools for preference elicitation. Furthermore, it highlighted the need to continue efforts concerning the fair aggregation of individual preferences, empowerment, and trust building. Finally, we will introduce our new digital tools that are available to the OR community: the ValueDecisions app to support complex decisions with MCDA, and online weight elicitation with the trade-off or Swing procedure.

Combining MCDA and Social Network Analysis to Understand Stakeholders in Swiss Pesticide Governance

• Milena Wiget, Karin Ingold, Judit Lienert
• Eawag
• Concerns about the risks of pesticides for human health and the environment are growing. Consequently, this topic is high on the water and agricultural policy agenda in Switzerland. Governing pesticides is a complex decision problem, which must address numerous objectives. Moreover, various stakeholders are involved who have different preferences towards these objectives. Pesticide governance also includes many uncertainties, which increase the challenge of decision-making. So far, the focus has mainly been on policy instruments and agricultural practices for pesticide use and risk reduction without considering all relevant objectives and stakeholders. For this purpose, we will use Multi-Criteria Decision Analysis (MCDA). In an online survey, we will elicit the preferences of relevant stakeholders towards the entire spectrum of objectives, and their risk attitude. We will also investigate what might influence these preferences and risk attitudes. To this end, we will combine MCDA with Social Network Analysis (SNA), a method from the political sciences. This includes questions about the stakeholders’ collaboration, information exchange, and information sources. Using SNA, we will then assess possible effects of these social interactions on stakeholders’ preferences, and vice versa. With the innovative combination of MCDA and SNA, we aim to gain a better understanding of the complex decision problem and involved stakeholders. Ultimately, we aim at identifying best governance options across various stakeholders in Swiss pesticide governance with a high potential for political consensus.

Comparing Different Rebalancing Operations Strategies in Car Sharing Systems

• Selin Ataç, Nikola Obrenović, Michel Bierlaire
• EPFL
• Car sharing (CS) services have become popular due to their financial and environmental benefits. The CS operators have offered flexibility by allowing one-way trips which resulted in vehicle imbalance in the service area. They have then introduced rebalancing operations to reduce the imbalance thus, to increase the level of service. In general, the methods studied in the literature focus on demand forecasting to determine the rebalancing strategy. However, in a dynamic system where the user behavior changes, evaluating different strategies and selecting the most appropriate one is essential. Therefore, this work proposes a framework which compares different strategies to solve rebalancing operations in one-way station-based car sharing systems in terms of cost and level of service. Since it is exhausting to collect the data to develop a demand model, we feed the trip demand output of Multi-Agent Transport Simulation Toolkit (MATSim) as an input to our framework. This also allows us to explore the different uncertainties that can occur in the system, such as fluctuations in trip demand. The results of the framework help the decision maker to better analyze the system and choose the best rebalancing policy under different scenarios.

A Service Intention in Public Transport with Integrated Travel Chains: Generation and Benefits

• Stephan Bütikofer
• ZHAW
• The public transport offer consists of a timetable for various train runs. The timetable is the final and detailed specification of the offer, it is computed based on a framework describing train runs and relationships between them (e.g. time intervals to be maintained between repetitions of train runs belonging to the same line). A formal description of this framework was introduced in the literature as service intention (SI). It was shown that the SI is a suitable input for the timetabling process. The SI includes technical and commercial parameters. Technical line properties are represented by linetypes and trip times. Commercial properties include dwell and transfer times and thus represent customer relevant service levels.
  In this presentation we discuss first a way to generate the SI using the typical strategic planning steps. Later we focus on the customer transfer relations, which are an important class of relations in the SI between train runs. By coordinating customer transfer relations, it becomes possible for customers to have one or more attractive travel chain between the origin and destination of their trip. A first modelling approach for travel chains will be discussed with the help of a current applied research project.