An Exact Approach for Selecting Pickup-Delivery Stations in Urban Areas to Reduce Distribution Emission Costs
This paper deals with a variant of the multifacility location-routing problem in urban areas. The distribution network is modelled by an undirected graph, in which the nodes are split into a set of pickup-delivery stations, a depot, and a set of customers. The arcs represent the minimum-cost connect...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-04-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/8/1876 |
| _version_ | 1827744596713537536 |
|---|---|
| author | Anna Sciomachen Maria Truvolo |
| author_facet | Anna Sciomachen Maria Truvolo |
| author_sort | Anna Sciomachen |
| collection | DOAJ |
| description | This paper deals with a variant of the multifacility location-routing problem in urban areas. The distribution network is modelled by an undirected graph, in which the nodes are split into a set of pickup-delivery stations, a depot, and a set of customers. The arcs represent the minimum-cost connections between nodes. A customer is assigned to a pickup-delivery station if he or she can reach it at the lowest sustainable cost, i.e., on foot or by bicycle, without exceeding a predefined maximum distance. The goal is to minimise the goods’ total delivery cost, including pollutant emissions. In this perspective, both travel distance and means of transport play a key role. We present an exact novel approach based on partitioning the research space of the solutions of a Mixed Integer Linear Programming model. In the model, Boolean decisional variables, representing the selection of the locations for the pickup-delivery stations, are fixed simultaneously with the solution of the classical Travelling Salesman Problem. A branching constraint allows us to determine the route that serves the selected pickup-delivery stations and the route, if any, that serves customers who do not go to any pickup-delivery station. We conduct extensive experimentation to test the proposed approach’s computational efficiency and analyse the optimal solution’s robustness with respect to the maximum distance of customers from the stations, their activation cost and the pollutant emissions. The effectiveness of the proposed approach in terms of solution quality and computation time is certified by a set of computational tests based on randomly generated instances with up to 150 customers and 30 pickup-delivery stations. The application of the proposed exact method to a case study related to a district of the city of Genoa (Italy) confirms its validity also for sustainably addressing real-size urban delivery problems. An evaluation of incentives for customers using pickup-delivery stations, possibly by implementing discount policies on orders, is also proposed. |
| first_indexed | 2024-03-11T04:47:05Z |
| format | Article |
| id | doaj.art-d31f9b8af4bd4f7e89e95aa973bc66b4 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T04:47:05Z |
| publishDate | 2023-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-d31f9b8af4bd4f7e89e95aa973bc66b42023-11-17T20:17:50ZengMDPI AGMathematics2227-73902023-04-01118187610.3390/math11081876An Exact Approach for Selecting Pickup-Delivery Stations in Urban Areas to Reduce Distribution Emission CostsAnna Sciomachen0Maria Truvolo1Department of Economics and Business Studies, University of Genoa, Via Francesco Vivaldi 5, 16126 Genoa, ItalyDepartment of Economics and Business Studies, University of Genoa, Via Francesco Vivaldi 5, 16126 Genoa, ItalyThis paper deals with a variant of the multifacility location-routing problem in urban areas. The distribution network is modelled by an undirected graph, in which the nodes are split into a set of pickup-delivery stations, a depot, and a set of customers. The arcs represent the minimum-cost connections between nodes. A customer is assigned to a pickup-delivery station if he or she can reach it at the lowest sustainable cost, i.e., on foot or by bicycle, without exceeding a predefined maximum distance. The goal is to minimise the goods’ total delivery cost, including pollutant emissions. In this perspective, both travel distance and means of transport play a key role. We present an exact novel approach based on partitioning the research space of the solutions of a Mixed Integer Linear Programming model. In the model, Boolean decisional variables, representing the selection of the locations for the pickup-delivery stations, are fixed simultaneously with the solution of the classical Travelling Salesman Problem. A branching constraint allows us to determine the route that serves the selected pickup-delivery stations and the route, if any, that serves customers who do not go to any pickup-delivery station. We conduct extensive experimentation to test the proposed approach’s computational efficiency and analyse the optimal solution’s robustness with respect to the maximum distance of customers from the stations, their activation cost and the pollutant emissions. The effectiveness of the proposed approach in terms of solution quality and computation time is certified by a set of computational tests based on randomly generated instances with up to 150 customers and 30 pickup-delivery stations. The application of the proposed exact method to a case study related to a district of the city of Genoa (Italy) confirms its validity also for sustainably addressing real-size urban delivery problems. An evaluation of incentives for customers using pickup-delivery stations, possibly by implementing discount policies on orders, is also proposed.https://www.mdpi.com/2227-7390/11/8/1876multi-facility location-routing problemmixed integer linear programming modelbranching criteriapickup-deliverysustainable logistics |
| spellingShingle | Anna Sciomachen Maria Truvolo An Exact Approach for Selecting Pickup-Delivery Stations in Urban Areas to Reduce Distribution Emission Costs Mathematics multi-facility location-routing problem mixed integer linear programming model branching criteria pickup-delivery sustainable logistics |
| title | An Exact Approach for Selecting Pickup-Delivery Stations in Urban Areas to Reduce Distribution Emission Costs |
| title_full | An Exact Approach for Selecting Pickup-Delivery Stations in Urban Areas to Reduce Distribution Emission Costs |
| title_fullStr | An Exact Approach for Selecting Pickup-Delivery Stations in Urban Areas to Reduce Distribution Emission Costs |
| title_full_unstemmed | An Exact Approach for Selecting Pickup-Delivery Stations in Urban Areas to Reduce Distribution Emission Costs |
| title_short | An Exact Approach for Selecting Pickup-Delivery Stations in Urban Areas to Reduce Distribution Emission Costs |
| title_sort | exact approach for selecting pickup delivery stations in urban areas to reduce distribution emission costs |
| topic | multi-facility location-routing problem mixed integer linear programming model branching criteria pickup-delivery sustainable logistics |
| url | https://www.mdpi.com/2227-7390/11/8/1876 |
| work_keys_str_mv | AT annasciomachen anexactapproachforselectingpickupdeliverystationsinurbanareastoreducedistributionemissioncosts AT mariatruvolo anexactapproachforselectingpickupdeliverystationsinurbanareastoreducedistributionemissioncosts AT annasciomachen exactapproachforselectingpickupdeliverystationsinurbanareastoreducedistributionemissioncosts AT mariatruvolo exactapproachforselectingpickupdeliverystationsinurbanareastoreducedistributionemissioncosts |