1,721,035 research outputs found
The Cost-Balanced Path Problem: A Mathematical Formulation and Complexity Analysis
No full textThis paper introduces a new variant of the Shortest Path Problem (SPP) called the Cost-Balanced Path Problem (CBPP). Various real problems can either be modeled as BCPP or include BCPP as a sub-problem. We prove several properties related to the complexity of the CBPP problem. In particular, we demonstrate that the problem is NP-hard in its general version, but it becomes solvable in polynomial time in a specific family of instances. Moreover, a mathematical formulation of the CBPP, as a mixed-integer programming model, is proposed, and some additional constraints for modeling real requirements are given. This paper validates the proposed model and its extensions with experimental tests based on random instances. The analysis of the results of the computational experiments shows that the proposed model and its extension can be used to model many real applications. Obviously, due to the problem complexity, the main limitation of the proposed approach is related to the size of the instances. A heuristic solution approach should be required for larger-sized and more complex instances
A Rich Vehicle Routing Problem for a City Logistics Problem
No full textIn 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. Thus, we deal with 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. In fact, 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 vehicles used. A mixed integer programming model is proposed, and an experimental campaign is presented for validating it. Tests have been used for evaluating the quality of the solutions in terms of both model behavior and service level to grant to the customers. Moreover, the benefits that can be obtained by postponing deliveries are evaluated. Results are discussed, and some conclusions are highlighted, including the possibility of formulating this problem in such a way as to use the general solver proposed in the recent literature. This seems to be the most interesting challenge to permit companies to improve the distribution activities
Grocery distribution plans in urban networks with street crossing penalties
No full textFollowing the emergency caused by the Covid-19 pandemic, there is the need, among other measures, to modify urban mobility plans in order to reduce the use of collective public transport, reducing the crowding of people while also preventing traffic congestion through discouraging the use of private vehicles. From this perspective, retail companies operating within cities must also reorganize themselves, considering both the unpredictable requirements of environmental sustainability and the new mobility needs calling for the promotion of bicycles and electric scooters. In this context, we deal with the need to determine minimum cost routes in urban areas for delivering orders placed through e-channels. More precisely, we face a variant of the green vehicle routing problem of heterogeneous fleets, in which the objective function includes environmental impact cost components that differ by vehicle type. Moreover, as a novel issue, attention must be paid to avoid crossing and passing close to bicycle lanes; therefore, penalties are associated with the transit of vehicles near bicycle lanes. To address this problem, we propose a mixed integer linear programming model and a matheuristic associated with it. The proposed approach is then used to analyze different scenarios derived from the transportation network of the city of Milan, Italy. Milan is one of the smartest cities in Europe from the mobility point of view but also one of the most affected by the Covid-19 pandemic, and the municipality is making a big investment to promote the use of bicycles
A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance
No full textThis paper addresses a variant of the classical Traveling Salesman Problem known as Close-Enough Traveling Salesman Problem. In this problem, there is a set of nodes (customers, targets), each of them associated with a region, denoted as neighborhood, that contains it. The goal is to determine the shortest tour that visits all the nodes, where a node is visited when the tour traverses or reaches the region associated with the node. We propose a genetic algorithm (GA), which uses several strategies to optimize the tour, such as 2opt, second-order cone programming, and a bisection algorithm. The proposed approach is tested on 62 benchmark instances. The results show that GA produces better or similar solutions compared to the ones produced by state-of-the-art algorithms in a reasonable computing time. Besides, GA found 32 new best solutions out of 62 instances. Furthermore, we propose different metrics to classify problem instances with the goal of detecting which problem characteristics have a larger impact on the difficulty of solving the problem. We also revised the already proposed metric, called Overlap Ratio, and correct its calculation done in previous contributions. Finally, we present a case study related to the diagnostic reconnaissance of solar panels. The case study is related to a research project developed at the University of Molise in collaboration with private IT companies. We show that the problem under study is properly modeled as a Close-Enough Traveling Salesman Problem and apply the GA to solve it, focusing on the benefits obtained by applying this solution approach
Min-cost route problems for multimodal sustainable logistics cooperation
No full textThis article addresses the pressing need for sustainable logistics practices in light of the current global climate emergency. Specifically, we tackle the problem of defining the shortest routes for various carriers in a multimodal logistics network while simultaneously reducing environmental impact. A novel aspect of our approach is that each transport demand from origin to destination is satisfied by considering all the routes within the multimodal network that intersect with the path associated with the transportation request. The primary goal is to minimise the number of circulating vehicles by fully utilising their available cargo capacity. To achieve this, we propose a mixed-integer linear programming model based on a multimodal graph. The objective function comprises various cost components, taking into account the transportation and service costs of different vehicle types (trucks, trains, ships, and aeroplanes). Additionally, the search for the optimal solution incorporates several parameters aligned with the paradigm of cooperative logistics and environmental sustainability. Specifically, pollutant emissions and payload utilisation are factored in through specifically tailored cost coefficients. A total of 3,240 test instances, derived from routes within the Italian multimodal transportation network, were generated and solved to optimality. The results underscore the effectiveness of the proposed model in addressing the aforementioned environmental concerns
Marine terraces in the Tyrrhenian Sea margin of the Southern Apennines (Italy): new constraints on differential vertical motions from dated paleoshorelines
No full textRelations, models and a memetic approach for three degree-dependent spanning tree problems
No full textAbstract In this paper we take into account three different spanning tree problems with degree-dependent objective functions. The main application of these problems is in the field of optical network design. In particular, we propose the classical Minimum Leaves Spanning Tree problem as a relevant problem in this field and show its relations with the Minimum Branch Vertices and the Minimum Degree Sum Problems. We present a unified memetic algorithm for the three problems and show its effectiveness on a wide range of test instances
Partitioning a street network into compact, balanced, and visually appealing routes
No full textIn practice, it is often desirable for the routes of vehicles to be compact and separate. A set of routes is compact if the streets serviced by each route are geographically clustered, and separated if the routes overlap minimally. We consider the Min–Max K Windy Rural Postman Problem (MMKWRPP), in which the objective is to route a homogeneous fleet of K vehicles such that the cost of the longest route is minimized. We develop a heuristic that is algorithmically simple, produces solutions that are comparable in quality to those produced by an existing approach, and performs well with respect to metrics that quantify compactness and separation. Our heuristic uses a partitioning scheme in which the weight of a vertex includes contributions from both incident streets requiring service and the distance needed to travel to a vertex. We present computational results for a set of instances that we generate from real-world street networks and for a set of artificial instances. Our code is part of the Open-source Arc Routing Library (OAR Lib) at https://github.com/Olibear/ArcRoutingLibrary. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(3), 290–303 2017
A two-stage solution approach for the Directed Rural Postman Problem with Turn Penalties
No full textIn this paper, we consider the Directed Rural Postman Problem with Turn Penalties (DRPP-TP). A solution is a tour that traverses all required arcs of the graph. The total cost of the tour is the sum of the lengths of the traversed arcs plus the penalties associated with the turns. One solution approach involves transforming the arc routing problem into an equivalent node routing problem. An alternative direct approach (without graph transformation) that involves two stages has been proposed in the literature. In the first part of this paper, we investigate the applicability of the direct approach. We identify several characteristics of the input instance that make this approach effective and present several limitations of this approach. In the second part of this paper, we describe an integer linear program that is combined with a local search algorithm. This combination produces high-quality solutions to the DRPP-TP in a reasonable amount of computing time. (C) 2018 Published by Elsevier B.V
Marine terraces in the Tyrrhenian Sea margin of the Southern Apennines (Italy): new constraints on differential vertical motions from dated paleoshorelines
Full text linkThe Neogene to Quaternary southern Apennines mountain belt is flanked to the SW by the Tyrrhenian Sea back-arc basin, which was formed since late Miocene times. Extensional tectonics related to back-arc basin formation affected the Tyrrhenian margin of the southern Apennines since the Quaternary with formation of a series of horst and graben structures. Huge amounts of existing surface, subsurface and offshore data indicate that subsidence on the order of thousands of metres affected the grabens, and remarkable flights of marine terraces are indicative of Quaternary uplift of the horst blocks. The highest and older marine terraces, Early Pleistocene in age, occur up to several hundreds of metres above the sea level.
A huge number of former studies have provided fundamental data on both the outcropping (raised) and buried paleoshorelines and littoral deposits, the chronological framework for the identified relative sea level fluctuations mostly rests on local-scale relative chronology reconstructions constrained by dating that are still quite rare and sparse.
Detail-scale geomorphological-geological mapping, integrated with Quaternary stratigraphy, aimed at the recognition, characterisation and dating of raised marine terraces and paleoshorelines (tidal notches, platform inner edges) has been carried out in several key areas of the southern Apennines Tyrrhenian Sea margin, from Campania, in the North, to northern Calabria, in the South. The field surveys have been carried out both in rocky coasts (where continental deposits cover and sometimes hide the paleoshorelines) and in the two main alluvial-coastal basins, namely the Campania and Sele River plains. The new geochronological data constrain the ages of several late Middle Pleistocene to Late Pleistocene sea level markers, allowing a better definition of the vertical motions in each study area. Overall, the time-space distribution of the vertical motions on the regional scale is better reconstructed, along with the framework of the Quaternary surface uplift of the southwestern slope of the southern Apennines mountain belt
- …
