Applications of OR I

Contributed Session

Time Slot: Tuesday Afternoon

Room: 003

Chair: Carlo Filippi

A Branch and Cut algorithm for the Flying Sidekick Traveling Salesman Problem

Time: 14:30

Maurizio Boccia (Università di Napoli “Federico II”), Mancuso Andrea, Masone Adriano, Sterle Claudio

Last mile logistics (LML) is one of the most important and expensive part of the freight dis-tribution process in a supply chain. LML role is not going to change in the future since we are observing an always increasing shift away from physical stores to digital shopping. In this context, the integration of new distribution technologies in the delivery systems, specifically drones, has been investigated by several companies to reduce the LML costs. The most prom-ising delivery system, in terms of emissions and completion time reduction, consists of a truck and a drone operating in tandem for the parcel delivery to the customers. These new drone-based delivery systems have led to the definition of new and complex decision and op-timization problems for which operations research methodologies represent a valuable sup-port tool. In this context, several contributions have appeared in the last years providing ILP and MILP formulations for these kinds of problems. Nevertheless, these formulations suffer from dimensional drawbacks which make their solution impracticable even on small instanc-es. In this work, we propose an exact approach for one of these problems, the flying sidekick traveling salesman problem (FS-TSP) [3]. It is a variant of the TSP where routing decisions are integrated with customer-to-drone and customer-to-truck assignment decisions and truck-and-drone synchronization constraints. The objective is the minimization of the time required to serve all the customers, considering drone payload capacity and battery power constraints. “Big-M” constraints to take into account the synchronization issue, are used by almost all the formulations proposed in literature [2]. In [1][4] the synchronization constraints are tackled in a column generation fashion. In this work a compact formulation without “Big-M” con-straints is presented and solved by using a Branch and Cut approach. The proposed method has been experienced on a large set of benchmark instances. Computational results show that it either is competitive or outperforms the best exact approach present in literature for the FS-TSP.

Real-time optimization for a Digital Twin of a robotic cell with human operator

Time: 14:50

Teresa Albini (Università degli Studi di Siena), Brocchi Andrea, Murgia Gianluca, Pranzo Marco

Digital Twins (DTs) can support the simulation, planning, and optimisation of the firm’s operations, but their adoption may be hindered by the role played by human operators. Indeed, differently from machines, human behaviours are largely characterized by nondeterministic nature, thus requiring that constant monitoring of the manufacturing system is accompanied by the development of real-time simulation and optimization algorithms.This paper presents the DT of a robotic cell for the manufacturing of Printed Circuit Boards (PCBs). The human operator oversees the management of the defective PCBs and the replenishment of the necessary materials for the cell but may also carry out some tasks otherwise performed by the robotic arm.The cell is autonomously optimized by the real time optimization algorithm keeping into account and adapting to the behaviour of the human operator. The optimization process guides the human operator by suggesting, without enforcing, the desired next moves. To deal with the uncertainty related to the human operator, we developed a simulation-optimization algorithm based on the Approximate Dynamic Programming framework. The algorithm evaluates the set of the available moves by simulating the behaviour of two independent agents (i.e., the robotic arm and the human operator) and selects the most promising moves for both these agents.Through an extensive experimental campaign and appropriate statistical analyses, we show how the productivity of the cell is scarcely affected by the behaviour of the human operator. These results may enrich the limited literature on DTs with human operators and provide useful insights to manufacturing companies interested in the implementation of robotic cells based on DTs.

A time-space multi-network modelling approach for the Location-Transshipment Problem in Synchromodal Logistics

Time: 15:10

Riccardo Giusti (Politecnico di Torino), Manerba Daniele, Crainic Teodor Gabriel

We study the tactical planning problem of a Logistics Service Provider (LSP) that must secure contracts with transshipment terminals for many months of operational activities. During that period the LSP needs to manage many customers’ origin-destination shipments through different types of services. The objective of the LSP is to minimize the costs for contracting and using the terminals plus the service costs to transport, handle, and store commodities. In the context of synchromodal logistics [1], we consider truck, rail, barge, and ship as available transport modes to perform long-haul shipments. An important synchromodality feature considered in our work regards the shipments’ flow synchronization addressed by considering penalties for late collection, early delivery, and late delivery. We first define a new MILP formulation variant of the classical Hub Location Problem [2], namely the Location-Transshipment Problem with Synchronized Multi-Commodity Flows. Then, we further model the problem using a time-space multi-network in which the time dimension and the time-dependent parameters are hidden within time-space nodes and arcs [3]. Given this model, we present an economic analysis to assess how much a more flexible environment, like the one required in the implementation of synchromodality, can affect operational costs. For this aim, we compare different types of instances in which some cost parameters vary depending on how much terminals and customers are flexible. Moreover, we present a solution method based on cutting-planes to overcome the computational limits of using a commercial solver as a black-box tool. We will present the validation of our modeling and solving methodology through an extensive computational campaign. Note that the modelling approach adopted could be relevant for other multi-periodic hub location problems.

[1] Giusti, R., Manerba, D., Bruno, G., Tadei, R., 2019. Synchromodal logistics: An overview of critical success factors, enabling technologies, and open research issues. Transportation Research Part E: Logistics and Transportation Review 129, 92–110.
[2] Alumur, S.A., Campbell, J.F., Contreras, I., Kara, B.Y., Marianov, V., O’Kelly, M.E., 2021. Perspectives on modeling hub location problems. European Journal of Operational Research 291, 1–17.
[3] Crainic, T.G., Hewitt, M., Toulouse, M., Vu, D.M., 2016. Service network design with resource constraints. Transportation Science 50, 1380–1393.

On crowd-shipping using public transport: MILP model and empirical evaluation

Time: 15:30

Carlo Filippi (Università degli Studi di Brescia)

Crowd-shipping is a promising shared mobility service that involve the delivery of goods using non-professional shippers [1]. One of the main goals of crowd-shipping initiatives is to reduce congestion and pollution in city centers. However, in most crowdshipping initiatives, the crowd rely on private motorized vehicles and hence the environmental benefits could be small, if not negative. Conversely, a crowd-shipping service relying on public transport should maximize the environmental benefits. Motivated by this observation, our aim is to model a crowd-shipping service based on public transport and to assess the potential economic impact of using bus- or met
ro-based crowd-shipping coupled with a traditional home delivery service.We consider a shipper that must deliver packages to customers located in an urban area served by a metro service using two delivery modes: home delivery and crowd-shipping. Home delivery is carried out by vehicles that visit customer locations; crowd-shipping is carried out by metro commuters using lockers located at the stations and supplied by the vehicles. A customer is compatible with crowd-shipping if her/his home is sufficiently close to a metro station and the required parcel is fitted for lockers. In this case, she/he can be served either by home delivery or by crowd-shipping. Otherwise, the customer must be served by home delivery. Essentially, the carrier has to decide: which customers to assign to crowd-shipping among those compatible with this delivery mode; how many vehicles are necessary to perform the delivery tasks; how to route the vehicles. We allow two crowd-shipment rewarding schemes: either fixed (possibly null) or proportional to the size of the package. The decision criterion for the carrier is total cost minimization.The resulting problem includes characteristics of the VRP with Occasional Drivers [2] and the VRP with Transshipment and Delivery Options [3]. We derive a MILP formulation including restrictions on the availability of crowd-shippers, locker capacity, and vehicle capacity. The model is implemented using Python with Gurobi solver and a computational study based on the municipalities of Brescia and Milan is performed. We get insights on the economic advantages that a metro-based crowd delivery option may have for a carrier, and we point out possible modeling and algorithmic developments.

[1] Le, T. V., Ukkusuri, S. V. (2019). Crowd-shipping services for last mile delivery: Analysis from American survey data. Transportation Research Interdisciplinary Perspectives, 1, 100008.
[2] Archetti, C., Savelsbergh, M., Speranza, M. G. (2016). The vehicle routing problem with occasional drivers. European Journal of Operational Research, 254(2), 472-480.
[3] Vincent, F. Y., Jodiawan, P., Redi, A. P. (2022). Crowd-shipping problem with time windows, transshipment nodes, and delivery options. Transportation Research Part E: Logistics and Transportation Review, 157, 102545.