Optimization on Graphs I

Contributed Session

Time Slot: Wednesday Afternoon

Room: AUD_A

Chair: Cristina Ondei

A multi period VRP for evaluating distribution strategies

Time: 17:30

Carmine Cerrone (University of Genoa), Anna Sciomachen, Daniela Ambrosino

In this work, a Rich Vehicle Routing Problem (RVRP) is faced for solving city logistic problems. In particular, we deal with the problem of a logistic company that has to define the best distribution strategy for obtaining an efficient usage of vehicles and for reducing transportation costs while serving customers with different priority demands during a given planning horizon [1]. Each customer’s demand is partitioned into three sets in accordance with different priorities. It is possible to split the customer demand. In this case, the split delivery consists in postponing the customer’s demand according to its priority. This problem can be defined as a multi-period vehicle routing problem with a heterogeneous fleet of vehicles, with customers’ requirements and company restrictions to satisfy, in which the fleet composition has to be daily defined. Actually, the company has a fleet of owned vehicles and the possibility to select, day by day, a certain number of vehicles from the fleet of a third-party company. Routing costs must be minimized together with the number of used vehicles. Only small instances can be solved up to optimality (i.e., instances with 20 customers). Thus, a heuristic approach based on a local search combined with a heuristic split of the input instance is proposed to solve this problem. A complete experimental campaign is presented for validating the proposed approach. Tests have been used for evaluating the quality of the obtained solutions. Moreover, the benefits that can be obtained by postponing deliveries are evaluated. Results are discussed, and some conclusions are highlighted.

[1] Ambrosino, D., Cerrone, C. A Rich Vehicle Routing Problem for a City Logistics Problem, (2022) Mathematics, 10 (2), art. no. 191.

Selection of pickup-delivery points in urban areas to reduce emission costs

Time: 17:50

Maria Truvolo (Università di Genova ), Anna Sciomachen Università di Genova

The problem of defining pickup-delivery points plays a crucial role in contemporary business development. Finding the optimal position to locate different assets of a company guarantees the reduction of the costs and emissions due to the logistical advantages that arise from the transport, storage and delivery of the goods. It also allows the expansion of the areas covered by the provided services by removing redundancies and narrowing the logistic gap between producers and consumers.[1]This work faces a variant of the classic multi-facility location problem represented by a graph, in which the set of nodes is partitioned into a set P of pickup-delivery points and a set C of customers. Customers must go to a node to pick up the required items. The number and the subset of the selected nodes of P are chosen with the goal of minimizing the total emission cost [2,3]. In this perspective, both travelling distance and means of transport (i.e., walking, bike, car, electrical vehicle, etc.) are considered. The fixed cost associated with the nodes in P is given. A customer C is assigned to a given node P if it can reach P at its minimum sustainable cost while not exceeding a predefined maximum distance between them. We present the model of the problem and develop a heuristic algorithm to produce effective solutions. The heuristic algorithm is based on a clusterization of the nodes. In order to perform extensively computational tests on realistic scenarios, we design an algorithm able to extract topological data from QGIS databases. The computational results are analyzed to certify the effectiveness of the produced approach in terms of quality of the solution and computational times.

[1] E. Ben Alaïa, I. H. Dridi, H. Bouchriha, and P. Borne, “Insertion of new depot locations for the optimization of multi-vehicles multi-depots pickup and Delivery Problems using Genetic Algorithm,” Proc. 2015 Int. Conf. Ind. Eng. Syst. Manag. IEEE IESM 2015, pp. 695–701, Jan. 2016.
[2] D. Ambrosino, A. Sciomachen, and M. G. Scutellà, “A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem,” Comput. Oper. Res., vol. 36, no. 2, pp. 442–460, Feb. 2009.
[3] E. Nathanail, M. Gogas, and G. Adamos, “Smart Interconnections of Interurban and Urban Freight Transport towards Achieving Sustainable City Logistics,” Transp. Res. Procedia, vol. 14, pp. 983–992, 2016.

Exact algorithms for the electric travelling salesman problem

Time: 18:10

Cristina Ondei (Dipartimento di Informatica, Università degli Studi di Milano), Ceselli Alberto, Righini Giovanni, Tresoldi Emanuele

Electric vehicles play an increasingly important role in transportation, making the design of adequate algorithms necessary.In the Electric TSP, a vehicle with a limited battery needs to visit a given set of clients. A set of recharge stations is also given, so that the vehicle can stop and recharge when necessary during the route. While clients must be visited only once, recharge stations can be visited multiple times. We consider a specific variant of this problem where multiple technologies (characterized by different costs and times per unit of recharge) are available at the single station.To solve it we consider two different exact techniques. The first approach is a branch-and-price algorithm, where every variable in the master problem represents a path (i.e. a sequence of clients) between two stations. The second method consists in a branch-and-cut algorithm.We experiment both algorithms on a set of instances from the literature, having different size, battery and time limits. This computational evaluation allows us to highlight the relative strengths and weaknesses of the two approaches.