Abstract
Sustainable transportation is one of the major challenges that modern countries are facing. Modern societies demand a high degree of mobility and the present transportation systems must evolve to ensure that people can move and freight can be transported in ways that are safe, cost-effective, and environmentally friendly. The number of private vehicles has increased for decades, and the ever-growing rise of e-commerce is generating an enormous demand for mobility of freight. Several projections foresee a continued growth of such a demand for mobility, which has been accelerated by the COVID-19 pandemic. Moreover, mobility players are collecting large amounts of data, thanks to cheap and connected devices such as smart phones, RFID readers, web-cams, and wireless sensors. The continuous data flow generated by these devices makes it possible to infer and to update time-dependent scenarios related to demand for service and traveling times. Finally, technical and socio-economic advances have made available a range of options for sustainability mobility (e.g., electric vehicles, intelligent transport systems, shared mobility), but still important hurdles must be overcome for their mass market adoption. As a result, mobility players, both from public (such as local authorities) and private sectors, are (and will be) facing increasingly complex managerial challenges, which urge the use of appropriate decision-support tools that aim at contributing to sustainability of mobility systems. This project aims at developing, implementing, and validating a set of time-dependent optimization tools that embraces different facets of mobility in urban areas. These tools will be based on new mathematical programming models and optimization algorithms, and aim at supporting the decisions of mobility players, in the context of sustainable mobility, taking advantage of the availability of dynamic time-dependent data. More in details, we will tackle the problem of determining an optimal deployment of charging stations for electric vehicles, by studying the variation during the day of recharging needs and the impact on the solutions of different urban layouts; we will address the problem of bike rebalancing in bike-sharing systems, by employing machine learning techniques to forecast user demand; we will study a new problem in freight delivery where an automated truck, along with a fleet of unmanned aerial vehicles, is employed; finally, we will study the problem of coordinating, in a dynamic setting, the directions to give to vehicles with the goal of reducing traffic congestion. The algorithms to solve these problems will be based on the solution, as sub-problems, of basic shortest path and routing problems. Hence, we will also develop efficient algorithms for the solution of constrained and time-dependent variants of the latter problems. Results The research activities of the RU-UNIBO were mainly concentrated on three of the work packages of the project, namely WP3, 5 and 6. Within WP3 we considered an important variant of Drone routing problem where the travel plan for a drone which has to visit a set of destinations has to be computed so as to minimize the total time required for the visits. The drone, which has a limited travel autonomy due to the small onboard batteries, has to synchronize its operation with a rover vehicle which serves as a mobile base where the drone can automatically exchange or replenish its batteries and then leave for a next set of visits. Such a drone-rover coordination makes the design of efficient travel plans extremely difficult, in particular when considering the short computing times which are typically available in real-world applications for the planning tasks. The studied problem is the Drone Routing Problem with Energy replenishment (DRP-E) which is a general class of routing problems with intermediate stops and synchronization constraints. In DRP-E, the drone has to visit a set of nodes and routinely requires battery swaps, energy or payload replenishment from mobile (i.e., the rover) or stationary replenishment stations. Thereby, the drone may visit several destinations between two replenishments, and mutual waiting at the rendezvous locations may occur. We developed a non-trivial search procedure, called VLNS, which examines this neighborhood entirely, in a computational time that remains polynomial in the problem size. VLNS is a flexible improvement procedure, which is easy to implement and can be adapted to many DRP-E variants. In computational tests, we demonstrated that a lean local-search-based implementation of VLNS already outperforms state-of-the-art heuristics for several DRP-E variants by a significant margin. We furthermore proposed a well-performing exact approach for DRP-E. The activities of the RU-UNIBO within WP5 faced two main research streams. In the first one we developed time-dependent shortest-path algorithms to compute travel times for each time period between every pair of user and station locations. These algorithms support the development of solution methods based on column generation techniques for a set of basic routing problems. Among the different TDSPPs, the research considered the following variants: • Minimum Arrival Time Path (MATP) problem, which minimizes the arrival time at the destination given the origin and the departure time. A common application of the MATP is the determination of the k-quickest routes to a destination under given traffic conditions, a functionality widely used in navigation applications. •Minimum Duration Path (MDP) problem, which identifies the path that minimizes the difference between the arrival time at the destination and the departure time at the origin, with neither the departure nor the arrival time fixed, but constrained within a given time horizon. •Minimum Travel Time Path (MTTP) problem, which aims to minimize the travel time between the origin and the destination, allowing waiting at vertices, although waiting time is not included in the objective function. •Minimum Cost Path (MCP) problem, in which arcs may be associated with both time-dependent travel time functions and time-dependent cost functions. The MCP aims to minimize the total cost rather than the total travel time. The RU-UNIBO proposed new Mixed-Integer Linear Programming (MILP) formulations for the considered TDSPPs, along with several exact methods for computing their k-best solutions. The research initially focused on the MATP, for which four mathematical models and both branch-and-bound and branch-and-cut algorithms were developed. These results were then extended to the MDP and the MTTP. The second research stream within WP5 considered a highly relevant practical problem related to the approximation of time-distance matrices in real-world routing applications. This research was performed in collaboration with Optit srl, a software company particularly active in the development of decision support systems for freight distribution and transportation. Practical routing applications, particularly those arising in city logistics and other smart routing applications, require the computation of routes for serving a huge number of customers, typically ranging between 500 to several thousands, where the set of customers to be served, as well as the traffic and road conditions, may vary considerably from one optimization to the other. As a consequence, huge time-distance matrices have to be computed very frequently as input data for the optimization. As this can be generally obtained by calling commercial APIs (such as Google Maps or Here) for each entry, thus requiring very long computing time and considerable storage which are not compatible with the short computing time available for the computation. In such a demanding context, the availability of sound techniques which allow for approximating the entries of the time-distance matrix by requiring just a limited number of calls to the commercial APIs, while preserving a good quality of the resulting approximate distances, plays a vital role in the successful use of routing software to support planning. The preliminary analysis of the literature showed that this research topic, despite its practical relevance, has attracted very little attention so far and the few existing approaches are far from being useful in modern routing assisted decision making. The RU-UNIBO has developed a framework for time-distance matrix estimation based on a clustering step in which customers are grouped in clusters through an exact clustering algorithm. The clustering exact algorithm is based on an innovative MILP model which computes a limited number of clusters and assigns to them the customers. The model due to its size is hard to solve and a specialized row/column generation (RCG) approach is developed to speed up its solution. Once clusters have been defined the time-distance matrix is computed by using the inter-cluster distances obtained by commercial APIs together with modified Euclidean distances where several different possible estimation formula were proposed. The approach was extensively tested on several large Capacitated VRP instances from the literature with thousands of customers and showed that matrix estimation, by using RCG clustering, can be obtained in a handful of seconds while computing the complete matrix may require hours and millions of API calls. Furthermore, when the approximate matrix is used as input to a high-quality heuristic, the obtained solutions are just slightly worse than those obtained by the same heuristic with the complete matrix.
Project details
Unibo Team Leader: Daniele Vigo
Unibo involved Department/s:
Dipartimento di Ingegneria dell'Energia Elettrica e dell'Informazione "Guglielmo Marconi"
Coordinator:
Università degli Studi di BRESCIA(Italy)
Total Unibo Contribution: Euro (EUR) 45.000,00
Project Duration in months: 24
Start Date:
28/09/2023
End Date:
28/02/2026
