1,720,998 research outputs found
Exact and heuristic algorithms for routing problems
No full textThis is a summary of the authors PhD thesis supervised by Daniele Vigo and defended on 30 March 2010, at the Università di Bologna. The thesis is written in English and is available from the author upon request. Several rich routing problems attaining to the transportation area have been studied. “Simple” algorithms have been proposed to solve them, both exact and heuristic, producing high quality solutions and transferrable method
The vehicle routing problem with release and due dates
No full textA novel extension of the classical vehicle routing and scheduling problems is introduced that integrates aspects of machine scheduling into vehicle routing. Associated with each customer order is a release date that defines the earliest time that the order is available to leave the depot for delivery and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimize a convex combination of the operational costs and customer service level, represented by the total distance traveled and the total weighted tardiness of delivery, respectively. A path-relinking algorithm (PRA) is proposed to address the problem, and a variety of benchmark instances are generated to evaluate its performance. The PRA exploits the efficiency and aggressive improvement of neighborhood search but relies on a new path-relinking procedure and advanced population management strategies to navigate the search space effectively. To provide a comparator algorithm to the PRA, we embed the neighborhood search into a standard iterated local search algorithm (ILS). Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem, and the performance of the PRA dominates that of the ILS algorithm
Glider Routing and Trajectory Optimisation in Disaster Assessment
Full text linkIn this paper, we introduce the Glider Routing and Trajectory Optimisation Problem (GRTOP), the problem of finding optimal routes and trajectories for a fleet of gliders with the mission of surveying a set of locations. We propose a novel MINLP formulation for the GRTOP. In our approach, we consider the gliders' flight dynamics during the definition of the routes. In order to achieve better convergence, we linearise the gliders' dynamics and relax the dynamic constraints of our model, converting the proposed MINLP into a MISOCP. Several different discretisation techniques and solvers are compared. The formulation is tested on 180 randomly generated instances. In addition, we solve instances inspired by risk maps of flooding-prone cities across the UK
Glider routing and trajectory optimisation in disaster assessment
No full textIn this paper, we introduce the Glider Routing and Trajectory Optimisation Problem (GRTOP), the problem of finding optimal routes and trajectories for a fleet of gliders with the mission of surveying a set of locations. We propose a novel MINLP formulation for the GRTOP. In our approach, we consider the gliders' flight dynamics during the definition of the routes. In order to achieve better convergence, we linearise the gliders' dynamics and relax the dynamic constraints of our model, converting the proposed MINLP into a MISOCP. Several different discretisation techniques and solvers are compared. The formulation is tested on 180 randomly generated instances. In addition, we solve instances inspired by risk maps of flooding-prone cities across the UK
An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times
No full textA conic-programing-based approach for trajectory optimisation of unmanned gliders
No full textIn recent years, employing Unmanned Aerial Vehicles (UAV) to collect data and make measurements has gained momentum. Often, the use of UAVs allows for a reduction in costs and improvements of other performance criteria. Those characteristics make UAVs suitable for disaster assessment, response and management. While the utilisation of powered UAVs has been broadly investigated in the literature, the employment of unpowered UAVs such as gliders has not been well explored. In fact, specialised control systems based on optimisation must be developed in order to guide such vehicles during their operations. In this paper we consider the problem of guiding a glider, along predetermined waypoints, in a wind field. We propose a Conic Programming Glider Trajectory Optimisation Problem, motivated by disaster assessment applications, and a solution framework. Some preliminary computational results are presented at the end of this work.</p
Disaster preparedness using risk-assessment methods from earthquake engineering
No full textAnalyzing the uncertainties associated with disaster occurrences is critical to make effective disaster preparedness plans. In this study, we focus on pre-positioning emergency supplies for earthquake preparedness. We present a new method to compute earthquake likelihood and the number of the affected people. Our approach utilizes forecasting methods from the earthquake engineering literature, and avoids using probabilistic scenarios to represent the uncertainties related to earthquake occurrences. We validate the proposed technique by using historical earthquake data from Turkey, a country under significant earthquake risk. We also present a case study that illustrates the implementation of our method to solve the inventory allocation problem of the Turkish Red Crescent
A Conic Programming-based approach for the trajectory optimisation of unmanned gliders
No full textIn recent years, employing Unmanned Aerial Vehicles (UAV) to collect data and make measurements has gained momentum. Often, the use of UAVs allows for a reduction in costs and improvements of other performance criteria. Those characteristics make UAVs suitable for disaster assessment, response and management. While the utilisation of powered UAVs has been broadly investigated in the literature, the employment of unpowered UAVs such as gliders has not been well explored. In fact, specialised control systems based on optimisation must be developed in order to guide such vehicles during their operations. In this paper we consider the problem of guiding a glider, along predetermined waypoints, in a wind field. We propose a Conic Programming Glider Trajectory Optimisation Problem, motivated by disaster assessment applications, and a solution framework. Some preliminary computational results are presented at the end of this work
Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs
No full textIn the well-known vehicle routing problem (VRP), a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two-commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instance
- …
