1,720,978 research outputs found
The multivisit drone routing problem with edge launches: An iterative approach with discrete and continuous improvements
No full textIn recent years, the usage of drones in last-mile logistics has stirred great interest in the operations research community. Many papers have considered schemes of hybrid truck-and-drone delivery. In this paper, we focus on the Multivisit Drone Routing Problem with Edge Launches (MVDRP-EL) which assumes: a heterogenous set of packages, a drone capable of carrying multiple packages at a time and that can be launched and retrieved along an edge, a flexible launch/retrieval site set, and a user-defined energy depletion function. We believe this paper is the first to exploit edge launch ability through a global continuous approach. In this context, we propose an original formulation based on the Covering Salesman Problem to compute a valid lower bound for the problem and an iterative solution method to determine a MVDRP-EL solution with quality launch/retrieval sites along the road network edges. Each iteration of the solution method consists of two phases. In the first phase, the road network edges are discretized to obtain launch/retrieval sites, and a first solution is determined. In the second phase, the truck route is set and we reduce the completion time by carefully synchronizing truck and drone routes by solving an original Mixed Integer Second Order Cone Program. The lower bound formulation and the proposed method have been tested on several instances and results indicate the effectiveness of the proposed method and the potential value of launching along an edge, respectively
Improved dynamic programming algorithms for unconstrained two-dimensional guillotine cutting
No full textIn the unconstrained two-dimensional cutting problem (U2DCP), we are given a large rectangular sheet to be cut in order to extract small rectangular pieces, with no limits on the number (demand) of desired pieces. We face the variant with guillotine constraint, requiring to cut any rectangle in two parts through vertical/horizontal cuts with end points on the rectangle boundaries. For a given U2DCP instance, the dynamic programming approach can be used either to optimally solve it, or to obtain a full matrix of upper bounds suitable for the constrained variant of the problem where limits exist on the piece demands. The elements of the full matrix are also usable as partial solutions to build lower bounds for the non-guillotine variant. In this paper, we propose two major improvements to a dynamic programming procedure previously shown to be capable of solving very large size instances. First, we introduce a new option for one of the three conditions used for the anti-redundancy strategies on cut coordinates. Second, following the effort of the Operations Research community to exploit the feature of modern CPUs containing multi-core processors, we provide a parallelization scheme. An extended computational campaign is presented. We compare the upgraded procedure with its previous version on a single thread and with the currently state-of-the-art algorithm for multi-thread platforms, outperforming both in terms of execution time on average by a factor of 1.7 and 12, respectively, or for some problem instances up to 4.5 and 50, respectively. Moreover, the new procedure can solve two very large instances previously unsolved, as well as the new huge instances proposed in this paper
A MILP Formulation for an Automated Guided Vehicle Scheduling Problem with Battery Constraints
No full textNowadays, AGVs are frequently used in industries for the internal transportation of goods or pallets. The aim of an AGV-based internal transportation system is to transfer the right amount of the right material to the right place at the right time. Therefore, the determination of a good scheduling of the AGV tasks is essential to overcome delays in production and material handling processes. In this work, we study a scheduling problem arising from an internal transportation system of a company operating in the manufacturing field where AGVs subject to battery constraints are used for horizontal movement of materials. The aim of this work is to highlight the impact of the AGV battery recharge times on the completion time of the material handling process. To this aim, we propose an original mixed integer linear programming (MILP) formulation to optimally solve the addressed problem. The proposed model is validated on test instances built from real data comparing its results with those obtained disregarding the battery constraints. The results show the effectiveness of the proposed solution method and the impact of the AGV charging time on the handling process completion time
A Feature Based Solution Approach for the Flying Sidekick Traveling Salesman Problem
No full textThe integration of new distribution technologies in the delivery systems, specifically drones, has been investigated by several companies to reduce the last mile logistic costs. The most promising delivery system, in terms of emissions and completion time reduction, consists of a truck and a drone operating in tandem for the parcel delivery to the customers. This has led to the definition of new and complex routing problems that have received great attention by the operations research community. Several contributions have appeared in the last years providing ILP and MILP formulation for these kinds of problems. Nevertheless, due to complexity, their solutions is impracticable even on small instances. In particular, the synchronization and the coordination of the two vehicles represent critical issues. In this work, we investigate the possibility of using customer characterizing features which allow to determine a priori promising customer-to-vehicle assignments. This information can be used to perform several variable fixings in the FSTSP formulation, so reducing the size and the complexity of the instances to be solved. Thus, the final aim is to determine optimal or sub-optimal solutions using state-of-the-art solver on a reduced FSTSP. To this aim, we provide a computational study proving the quality of the chosen features and their effectiveness in the solution of new and literature instances
A column-and-row generation approach for the flying sidekick travelling salesman problem
No full textThe flying sidekick traveling salesman problem (FS-TSP) is a parcel delivery problem arising in the last-mile logistics, where the distribution plan of a driver-operated truck assisted by a drone (unmanned aerial vehicle, UAV) has to be defined. The FS-TSP is a variant of the TSP where routing decisions are integrated with customer-to-drone and customer-to-truck assignment decisions and truck-and-drone synchronization constraints. The objective is the minimization of the time required to serve all the customers, taking into account drone payload capacity and battery power constraints. In this work we provide a new representation of the FS-TSP based on the definition of an extended graph. This representation allows to model the problem by a new and compact integer linear programming formulation, where the synchronization issue is tackled in a column generation fashion, thus avoiding the usage of big-M constraints, representing one of the main drawbacks of the models present in literature. The proposed formulation has been solved by an exact approach which combines a Branch-and-Cut algorithm and a column generation procedure, strengthened by variable fixing strategies and new valid inequalities specifically defined for the problem. The proposed method has been experienced on a large set of benchmark instances. Computational results show that the proposed approach either is competitive or outperforms the best exact approach present in literature for the FS-TSP. Indeed, it is able to provide the optimal solution for all small size instances with 10 customers and for several medium size instances with 20 customers, some of them never solved before
An Exact Approach for a Variant of the FS-TSP
No full textIn this work we focus on the flying sidekick traveling salesman problem (FS-TSP). The FS-TSP arises in the last-mile distribution context and it is a variant of the TSP aimed at determining the distribution plan of a driver-operated truck assisted by a drone (unmanned aerial vehicle, UAV), where the synchronization between the two vehicles allows to parallelize the delivery operations, so providing a reduction of the overall completion time. Several variants of the FS-TSP have been considered in literature, most of them sharing the assumption that launching and rendezvous position of a drone sortie must be different. In this work, we relax this assumption allowing the truck to wait for the drone at the launching position (FS-TSP*). This introduces an important flexibility element to deal with deliveries in rural or in urban areas with no-fly zones. We propose an original and compact integer linear programming formulation which allows to exactly solve the FS-TSP*and consequently also the FS-TSP. The results on several test instances show that our method can effectively solve to optimality instances with up to 20 customers and quantify the advantages of the FS-TSP*with respect to FS-TSP in terms of overall completion time
OPS4Math project-Optimization and Problem Solving for Teaching of Mathematics: Teaching strategy, organization and
No full textSeveral initiatives have been implemented worldwide to foster student interest towards STEM disciplines. These initiatives are based on the awareness that mathematics is essential for scientific and technological advancement: it trains to reasoning and reflection, stimulates logical capabilities and intuition, improve investigation attitude. Most of them recognize also that mathematical problem solving represents an effective way to support teachers and students in their teaching and learning activities, respectively. In this context, this work is aimed at presenting OPS4Math (Optimization and Problem Solving for Teaching of Mathematics), a training project for Secondary School teachers, supported by Italian Ministry of University and Research. The driving idea, widely discussed by the scientific community, is to operate a reversal of the didactical perspective: starting from phenomena/problems to introduce concepts of data, variables, relationships and functions in an appealing way. We present project organization, structure and aims, to give useful hints for its
replication
Empirical Investigation on Knowledge Packaging supporting Risk Management in Software Processes
No full textProject risks management is a non trivial task based on manager experience and knowledge collected in past executed projects. The larger the project manager experience and the available enterprise risk knowledge, the better the enterprise ability in risk management will be. For this reason the scientific community has focused its attention on the identification of methods, tools, and techniques for formalizing experience and know-how and making it available for other projects. In this sense, the authors have already presented a Risk Knowledge Package [1] for managing risk knowledge during software process execution. The work here proposed represents the continuation of such studies. In particular, an empirical investigation in industrial field has been carried out. Such investigation, based on legacy projects of EDS Italia Software SpA, aims at validating the effectiveness and the precision of the proposed approach. The results obtained encourage and stimulate further investigations in different software contexts
A MILP Formulation for the Reorganization of the Blood Supply Chain in Italian Regions
No full textBlood is a vital resource for human being since its unavailability may cause deaths and complications for patients. For this reason, in the last 20 years great interest has been addressed worldwide to the blood supply chain management, in terms of efficient and effective policy making and system design.
In answer to this raising need, the Italian Healthcare Ministry issued a decree aimed at improving the blood supply chain at regional level in terms of costs, accessibility and shortage, providing also several indications and restrictions to be accounted for. In this context, this chapter presents a mixed-integer linear programming formulation to determine the optimal location and the number of blood facilities at regional scale, with the aim of minimizing system costs meanwhile guaranteeing good standard service level requirements.
The proposed formulation tackles the problem in a multi-echelon and multi-objective perspective. It has been solved by Gurobi 9.0.1 solver and validated on real like test cases related to Campania and Puglia regions. Finally, the impacts of the different parameters involved in the formulation are analyzed in order to provide managerial insights to decision makers and healthcare stakeholders
A Location-Routing Based Solution Approach for Reorganizing Postal Collection Operations in Rural Areas
No full textPostboxes generally represent a cost for a postal service provider since they require to be maintained and daily visited by an operator to collect the letters. On the other hand, for the users, they are the main access points to the postal network and so the reduction of their number could result in a deterioration of the quality of the service for them. This work addresses a real problem involving the reduction of the number of postboxes located in rural areas to reorganize the collection operations of a postal service provider. We formulate this problem as a location-routing problem where the number of postmen employed is minimized guaranteeing the user accessibility. Exact and heuristic solution methods have been developed, tested and compared to existing solution methods on instances based on real data of rural instances showing the effectiveness of the proposed methodologies
- …
