1,720,990 research outputs found
VRP in urban areas to optimize costs while mitigating environmental impact
No full textNowadays, the need to think about sustainable mobility, both goods and people, is widely recognized. For this reason, many recent papers have moved in this direction. In this context, particular attention is now devoted to urban mobility, mainly from a smart city perspective. The present work focuses on sustainable urban freight distribution and proposes a variant of the VRP, which presents some innovative aspects. The goal is to minimize the routes’ cost components, including traveling and external costs due to environmental issues, depending on the chosen vehicles and the different urban streets to cross. In addition, restrictions on the maximum duration of each route to ensure frequent sanitation of vehicles used for deliveries, as required from the beginning of the COVID-19 pandemic, are imposed. The distribution network is modeled by a weighted digraph for which some properties are proved. To face the problem, we present a mixed-integer linear programming model, a math-heuristic associated with it, and a memetic algorithm approach. The results of the reported computational experimentation with random instances specifically tailored for the problem show the efficiency of the proposed methods. Further, test cases based on data of the distribution network of two B2C companies operating in the city of Genoa, Italy, proved the effective application of the proposed methods in the direction of sustainable urban distribution plans
Optimising transportation plans for multi-warehouse, multi-product systems: mitigating the impact of new purchase and sales orders
No full textIn the rapidly evolving landscape of supply chain management, the agility to adapt to changing demands while maintaining operational efficiency is paramount. This paper introduces a novel approach to managing transportation plans within a multi-warehouse, multi-product framework, focussing on minimising disruptions to existing schedules in response to new purchase and sales orders. Our research aims to redefine existing transportation plans, originally set before the arrival of additional orders, with the objective of implementing the least possible alterations while satisfying all customer requirements. The primary challenge addressed in this study is to maintain stock levels above a predefined minimum threshold in various warehouses without compromising the efficiency of the distribution network. Unlike traditional routing problems, the focus is not on selecting the routes for transportation, but on strategically deciding when to initiate a vehicle trip or adjusting the number of products in already scheduled trips. To address the problem, a mixed-integer linear programming model based on a flow network graph is proposed. To reduce the size of the network, exact and heuristic pre-processing procedures are developed. A first set of computational tests was conducted on data provided by a textile industry that needs to minimise changes in the transport plan to meet the variation in demand for different goods. A detailed analysis of the results of instances with up to 14,000 products and 23 million items is reported. Further computational tests were randomly generated to verify the efficiency of the proposed techniques in different scenarios. The promising results of the computational tests highlight the applicability of the proposed approach in the industrial scenario analysed
Integrating Human-Centric AI in Fashion Industry Optimization: A Step Towards Industry 5.0
No full textThis work explores the intersection of advanced manufacturing and the emerging human-centric Industry 5.0 paradigm, specifically within the high-fashion clothing industry. We address the critical issue of optimising cutting operations, a traditionally time-intensive and wasteful process, by minimising setup times and reducing fabric waste. The cutting process primarily consists of laying multiple layers of fabric on a cutting machine and securing templates (stencils) of the parts on top of these layers before the actual cutting can start. We introduce a novel solution that blends the technological advances of Industry 4.0, particularly the integration of mathematical models and the enterprise information system, with the worker-focused ethos of Industry 5.0. The core innovation lies in our use of Large Language Models to translate operators’ feedback, expressed in natural language, into quantifiable objectives for linear programming optimisation algorithms. The experimental analysis, conducted on a real-world industrial dataset, validates the effectiveness of the proposed solution, underscoring its potential to enhance industrial operations by harmoniously blending advanced technology with human well-being
A Branch & Bound Algorithm for the Rainbow Spanning Forest Problem
No full textIn this paper, we present a Branch & Bound algorithm for solving an NP-hard combinatorial optimisation problem denoted as Rainbow Spanning Forest Problem (RSFP). The RSFP consists of finding a spanning forest of an undirected, edge-coloured graph G with the minimum number of rainbow components, where a rainbow component of G is a subgraph of G that has all the edges with different colours. The proposed method is capable of determining the optimal solution within 0.4 s for small instances, thus proving to be computationally competitive with respect to the methods used by the most recent optimisation libraries and commercial SW environments available
An Adaptive Heuristic Approach to Compute Upper and Lower Bounds for The Close-Enough Traveling Salesman Problem
Get PDFThis paper addresses the close-enough traveling salesman problem, a variant of the Euclidean traveling salesman problem, in which the traveler visits a node if it passes through the neighborhood set of that node. We apply an effective strategy to discretize the neighborhoods of the nodes and the carousel greedy algorithm to appropriately select the neighborhoods that, step by step, are added to the partial solution until a feasible solution is generated. Our heuristic, based on these ingredients, is able to compute tight upper and lower bounds on the optimal solution relatively quickly. The computational results, carried out on benchmark instances, show that our heuristic often finds the optimal solution, on the instances where it is known, and in general, the upper bounds are more accurate than those from other algorithms available in the literature
The Trigger Arc TSP: Optimise the Picking Process in Warehouses with Compactable Storage Systems
No full textThis work introduces the Trigger Arc Travelling Salesman Problem (TATSP), a variant of the classical TSP that models dynamic arc costs influenced by the solution’s path. It is presented a real-world application that can be modelled through the TATSP, aiming to optimise operations in warehouses with compactable storage systems. An Integer Linear Programming model (ILP) is described and implemented. Finally, the experimental results obtained from a set of generated instances are discussed
A novel discretization scheme for the close enough traveling salesman problem
Get PDFThis paper addresses a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood set of that node. The problem is known as the close-enough traveling salesman problem. We introduce a new effective discretization scheme that allows us to compute both a lower and an upper bound for the optimal solution. Moreover, we apply a graph reduction algorithm that significantly reduces the problem size and speeds up computation of the bounds. We evaluate the effectiveness and the performance of our approach on several benchmark instances. The computational results show that our algorithm is faster than the other algorithms available in the literature and that the bounds it provides are almost always more accurate
Relations, 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
Vehicle-ID sensor location for route flow recognition: Models and algorithms
Get PDFWe address an important problem in the context of traffic management and control related to the optimum location of vehicle-ID sensors on the links of a network to derive route flow volumes. We consider both the full observability version of the problem, where one seeks for the minimum number of sensors (or minimum cost) such that all the route flow volumes can be derived, and the estimation version of the problem, that arises when there is a limited budget in the location of sensors. Four mathematical formulations are presented. These formulations improve the existing ones in the literature since they better define the feasible region of the problem by taking into account the temporal dimension of the license plate scanning process. The resulting mathematical formulations are solved to optimality and compared with the existing mathematical formulations. The results show that new and better solutions can be achieved with less computational effort. We also present two heuristic approaches: a greedy algorithm and a tabu search algorithm that are able to efficiently solve the analyzed problems and they are a useful tool able to find a very good trade-off between quality of the solution and computational time
- …
