Optimization on Graphs II

Contributed Session

Time Slot: Thursday Morning

Room: AUD_A

Chair: Victor Hugo Vidigal Corrêa

Optimal Network Design for Waste Management in Regional Districts: the PIPER Project

Time: 9:00

Diego Maria Pinto (IASI-CNR), Marco Boresta, Annalivia Croella, Claudio Gentile, Laura Palagi, Giuseppe Stecca, Paolo Ventura

Waste management (WM) optimization is one of the key tasks to realize circular economy and achieve sustainability in large metropolitan areas. In this regard, location models are one of the main quantitative tools for spatial planning of service networks and, in combination with other methods such as data analytics and simulation, they can be effectively used in order to support network reengineering processes. Considering the WM setting, these models are able to support the reality of decision making whenever they also take into account the underlying network changes such as demand evolution, cost patterns modifications, transport and facility technology progresses.This work proposes a network design model for a large metropolitan area, as a part of regional research project named PIPER – Intelligent Platform for the Optimization of Recycling Operations (grant n. A0375-2020-36611). The project aims at exploiting advanced applied research in the fields of optimization and artificial intelligence, and to apply them to the problems related to the sustainability of recycling processes, in terms of environmental, social, end economic targets. The reengineering of the waste management network allows the optimization of specific objectives, such as network crossing times, costs and waitings, while satisfying a variety of constraints both of recycling performance and of financial balance. Costs evaluation will take into account both facilities construction and maintenance costs and the transportation costs through the network. In the reengineered network a key role is played by the so called transshipment locations, facilities used to lower the time spent by collection vehicles travelling the network instead of collecting waste bins. The models take into consideration the regional allocation of waste storage, treatment and selection plants, the distribution and concentration of urban agglomerations and industrial districts. Regarding the type of facilities, we distinguish waste sorting plants, waste-to-energy plants, composting plants, incineration plants and landfills. These models can indeed suggest the location of a new facility based on the demand, the variability and the type of urban and industrial waste produced in the area.Thus, applying the principles of self-sufficiency and proximity to disposal, we proceeded to the definition of mathematical models useful for recommending the type of strategic and operational interventions required to improve a regional waste management network.Some of the environmental indicators and data used are the same monitored by the regional agency for environment protection ARPA, by the Italian agency ISPRA and by AMA Spa, the main logistic player in the region in question and one of the the biggest WM companies in Europe.

A preliminary approach to the short-length time-slotted routing topologies problem

Time: 9:20

Cristina Requejo (University of Aveiro), Pereira António

The data transmission process is of the utmost importance nowadays and consists of transferring data between digital devices. The process enables devices or components within devices to communicate between them and occurs via point-to-point data streams or channels. These channels may previously have been in the form of copper wires but are now much more likely to be part of a wireless network. The way data is transmitted by these channels is regulated through protocols such as the Time Slotted Channel Hopping (TSCH). This is one of the medium access control modes that is defined in IEEE 802.15.4e standard, a protocol designed for the Industrial Internet of Things (IIoT) applications such as smart city, smart home, and smart factory.Data transmission in TSCH networks is performed according to a tight time schedule. The higher the time schedule length, the higher the energy consumption of the network nodes and the end-to-end transmission delay. The amount of data transferred within a given time period is the data transfer rate, which dictates whether or not a network supports tasks that require complex, data-intensive applications. A higher data throughput improves user experience and increases reliability. Thus is important the use of short-length time-slotted routing topologies. In this work, we consider the problem of finding tree routing topologies that minimize the time-slotted length. We are given a network and a set of data packets that need to be sent to the root node. In order to reduce interferences, each node is active at most one time at each time-slotted (half-duplex) and once a packet is sent, it never stops and goes directly to the root node. The objective function, to be minimized, is the time-slotted length. We characterize the problem, propose a mixed integer linear programming formulation, and evaluate the influence of the characteristics of the problem on the solution. A computational experience is carried out to assess the solutions obtained and the proposed solution strategies.

MaaS network pricing with non-cooperative transportation service providers

Time: 9:40

David Rey (SKEMA Business School, Universite Cote d’Azur, Sophia Antipolis, France), Jian Sisi, Huang Wentao

We address a pricing problem in the context of Mobility-as-a-Service (MaaS). The past decade has witnessed a significant increase in the diversity of urban mobility services. Ranging from conventional mass transportation, to shared mobility and on-demand transit services, these mobility solutions coexist and compete with each other in transportation networks. MaaS is an emerging business model that aims to integrate multimodal transportation solutions and provide seamless mobility solutions to users. This motivates the study of path-based pricing mechanisms where users are charged based on their path choice in a multimodal transportation network. Yet, most studies on MaaS have thus focused on characterizing travelers’ demand for this new service scheme rather than on providing optimized pricing mechanisms. In this study, we consider a multimodal transportation network where nodes of the network represent trip origins, destinations, or transfer hubs across transportation services. Two nodes may be connected by one or more links representative of different transportation modes. We consider a set of trips representative of origin and destination pairs in the network with known travel demand. Each trip can be accomplished by traveling onto a path in the network connecting the origin and the destination of this trip. We model paths’ attractiveness using generalized cost functions that combine path travel time and path cost. We consider that reserve mobility alternatives outside of the MaaS network are available and we use linear elastic travel demand functions to capture the proportion of demand served by a path. Links of the network are assumed to be controlled by multiple profit-maximizing transportation service providers (TSPs). TSPs can adjust link fares to increase revenue subject to link capacity constraints. We take the perspective of a network regulator which aims to maximize ridership in the MaaS network by providing path-based subsidies to users while anticipating the strategies of non-cooperative TSPs and their effect on path generalized costs. This sets the basis for a Stackelberg game model wherein the leader player represents the network regulator and multiple follower players represent the TSPs. This game-theoretical framework is known as a single leader multi-follower game (SLMFG). We conduct a theoretical analysis of this SLMFG by identifying necessary and sufficient conditions for the existence of solutions to th
e parameterized generalized Nash equilibrium problems (GNEP) that is played amongst TSPs. Notably, we show that this GNEP is jointly convex and use this property to develop an exact numerical approach to solve the SLMFG. Numerical results reveal the impact of TSP competition in this MaaS network pricing problem and shed novel insights into the design of optimal path-based subsidy policies. We also investigate how subsidies can be designed to promote equity in the MaaS network.

Path planning for autonomous vehicles in smart wherehouses

Time: 10:00

Davide Donato Russo (Università degli Stude del Molise), Cerrone Carmine, Perea Rojas-Marcos Federico

Autonomous vehicles are becoming a reality in controlled scenarios thanks to the fast growth of technologies. They are largely used, for example, in autonomous warehouses or automated city transport systems. In this work, we present the Concurrent Shortest Path Problem. It is a variant of the Shortest Path Problem in which, given a discretized time horizon, is possible to handle multiple shortest paths, while avoiding collisions between vehicles. The aim of the problem is to minimize the total path length while avoiding collisions on nodes. We present two formulations for the problem. The first, consider a multilayer temporal graph, and the second is inspired by the bin packing problem. A deep comparison of these two formulations is performed, to analyze which one works better under which conditions. Finally, several tests were performed to assess the effectiveness of the proposed approaches.

An Iterated Local Search Algorithm for a Multi-period Orienteering Problem Arising in Car Patrolling

Time: 10:20

Victor Hugo Vidigal Corrêa (Federal University of Viçosa), Dong Hang, Iori Manuel, Gustavo dos Santos André, Yagiura Mutsunori, Zucchi Giorgio

In this work, we address a real-life multi-period orienteering problem arising in a large Italian company that needs to patrol a vast area in order to provide security services. The area is divided into clusters, and each cluster is assigned to a patrol. A cluster comprises a set of customers, each requiring different services on a weekly basis. Some services are mandatory, while others are optional. It might be impossible to perform all optional services, and each of them is assigned a score when performed. The problem is to determine a set of routes, one for each patrol and each day, that maximizes the total collected score, while meeting a number of operational constraints, including hard time windows, maximum riding time, and minimum time between two consecutive visits for the same service at the same customer. To solve the problem, we propose a mixed integer linear programming (MILP) model and an iterated local search (ILS) algorithm. The ILS invokes at each iteration an inner variable neighborhood descent (VND) procedure. While the ILS uses large neighborhood structures to shake the solution, the VND uses a set of more specialized neighborhood structures in order to lead the solution to an improved locally optimal solution.The performance of a commercial solver on the MILP model and of the ILS heuristic was assessed by testing them on a large set of real-life instances, from several provinces in Italy, provided by the company. The MILP model was solved by using Gurobi 9.5 and was able to find optimal solutions for small-size instances in a two-hour time limit. For larger-size instances, the ILS heuristic yielded better solutions than Gurobi. The solutions produced by the ILS were also better than those practically in use at the company for all instances that were addressed.