The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery

Once limited to the military domain, unmanned aerial vehicles are now poised to gain widespread adoption in the commercial sector. One such application is to deploy these aircraft, also known as drones, for last-mile delivery in logistics operations. While significant research efforts are underway to improve the technology required to enable delivery by drone, less attention has been focused on the operational challenges associated with leveraging this technology. This paper provides two mathematical programming models aimed at optimal routing and scheduling of unmanned aircraft, and delivery trucks, in this new paradigm of parcel delivery. In particular, a unique variant of the classical vehicle routing problem is introduced, motivated by a scenario in which an unmanned aerial vehicle works in collaboration with a traditional delivery truck to distribute parcels. We present mixed integer linear programming formulations for two delivery-by-drone problems, along with two simple, yet effective, heuristic solution approaches to solve problems of practical size. Solutions to these problems will facilitate the adoption of unmanned aircraft for last-mile delivery. Such a delivery system is expected to provide faster receipt of customer orders at less cost to the distributor and with reduced environmental impacts. A numerical analysis demonstrates the effectiveness of the heuristics and investigates the tradeoffs between using drones with faster flight speeds versus longer endurance.     

Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign AVs to immediate traveler demand requests

Motivated by the growth of ridesourcing services and the expected advent of fully-autonomous vehicles (AVs), this paper defines, models, and compares assignment strategies for a shared-use AV mobility service (SAMS). Specifically, the paper presents the on-demand SAMS with no shared rides, defined as a fleet of AVs, controlled by a central operator, that provides direct origin-to-destination service to travelers who request rides via a mobile application and expect to be picked up within a few minutes. The underlying operational problem associated with the on-demand SAMS with no shared rides is a sequential (i.e. dynamic or time-dependent) stochastic control problem. The AV fleet operator must assign AVs to open traveler requests in real-time as traveler requests enter the system dynamically and stochastically. As there is likely no optimal policy for this sequential stochastic control problem, this paper presents and compares six AV-traveler assignment strategies (i.e. control policies). An agent-based simulation tool is employed to model the dynamic system of AVs, travelers, and the intelligent SAMS fleet operator, as well as, to compare assignment strategies across various scenarios. The results show that optimization-based AV-traveler assignment strategies, strategies that allow en-route pickup AVs to be diverted to new traveler requests, and strategies that incorporate en-route drop-off AVs in the assignment problem, reduce fleet miles and decrease traveler wait times. The more-sophisticated AV-traveler assignment strategies significantly improve operational efficiency when fleet utilization is high (e.g. during the morning or evening peak); conversely, when fleet utilization is low, simply assigning traveler requests sequentially to the nearest idle AV is comparable to more-advanced strategies. Simulation results also indicate that the spatial distribution of traveler requests significantly impacts the empty fleet miles generated by the on-demand SAMS.     

Effects of a hovering unmanned aerial vehicle on urban soundscapes perception

Several industry leaders and governmental agencies are currently investigating the use of Unmanned Aerial Vehicles (UAVs), or ‘drones’ as commonly known, for an ever-growing number of applications from blue light services to parcel delivery. For the specific case of the delivery sector, drones can alleviate road space usage and also lead to reductions in CO₂ and air pollution emissions, compared to traditional diesel-powered vehicles. However, due to their unconventional acoustic characteristics and operational manoeuvres, it is uncertain how communities will respond to drone operations. Noise has been suggested as a major barrier to public acceptance of drone operations in urban areas. In this paper, a series of audio-visual scenarios were created to investigate the effects of drone noise on the reported loudness, annoyance and pleasantness of seven different types of urban soundscapes. In soundscapes highly impacted by road traffic noise, the presence of drone noise lead to small changes in the perceived loudness, annoyance and pleasantness. In soundscapes with reduced road traffic noise, the participants reported a significantly higher perceived loudness and annoyance and a lower pleasantness with the presence of the same drone noise. For instance, the reported annoyance increased from 2.3 ± 0.8 (without drone noise) to 6.8 ± 0.3 (with drone noise), in an 11-point scale (0-not at all, 10-extremely). Based on these results, the concentration of drone operations along flight paths through busy roads might aid in the mitigation of the overall community noise impact caused by drones.     

Comparison of energy demands of drone-based and ground-based parcel delivery services

Drones are one of the most intensively studied technologies in logistics in recent years. They combine technological features matching current trends in transport industry and society like autonomy, flexibility, and agility. Among the various concepts for using drones in logistics, parcel delivery is one of the most popular application scenarios. Companies like Amazon test drones particularly for last-mile delivery intending to achieve both reducing total cost and increasing customer satisfaction by fast deliveries. As drones are electric vehicles, they are also often claimed to be an eco-friendly mean of transportation.In this paper an energy consumption model for drones is proposed to describe the energy demand for drone deliveries depending on environmental conditions and the flight pattern. The model is used to simulate the energy demand of a stationary parcel delivery system which serves a set customers from a depot. The energy consumed by drones is compared to the energy demand of Diesel trucks and electric trucks serving the same customers from the same depot.The results indicate that switching to a solely drone-based parcel delivery system is not worthwhile from an energetic perspective in most scenarios. A stationary drone-based parcel delivery system requires more energy than a truck-based parcel delivery system particularly in urban areas where customer density is high and truck tours are comparatively short. In rather rural settings with long distances between customers, a drone-based parcel delivery system creates an energy demand comparable to a parcel delivery system with electric trucks provided environmental conditions are moderate.     

The impact of depot location,fleet composition and routing on emissions in city logistics

This paper investigates the combined impact of depot location, fleet composition and routing decisions on vehicle emissions in city logistics. We consider a city in which goods need to be delivered from a depot to customers located in nested zones characterized by different speed limits. The objective is to minimize the total depot, vehicle and routing cost, where the latter can be defined with respect to the cost of fuel consumption and CO₂ emissions. A new powerful adaptive large neighborhood search metaheuristic is developed and successfully applied to a large pool of new benchmark instances. Extensive analyses are performed to empirically assess the effect of various problem parameters, such as depot cost and location, customer distribution and heterogeneous vehicles on key performance indicators, including fuel consumption, emissions and operational costs. Several managerial insights are presented.     

A decomposition-based iterative optimization algorithm for traveling salesman problem with drone

This study investigates a new delivery problem that has emerged after the attempts of several e-commerce and logistics firms to deploy drones in their operations to increase efficiency and reduce delivery times. In this problem, a delivery truck that carries a drone on its roof serves customers in coordination with a drone. The drone is considered to complement the truck due to its cost-efficiency and ability to access difficult terrains and to travel without exposure to congestion. This study presents an iterative algorithm that is based on a decomposition approach to minimize delivery completion time. In the first stage of the proposed methodology, the truck route and the customers assigned to the drone are determined. In the second stage, a mixed-integer linear programming model is solved to optimize the drone route by fixing the routing and the assignment decisions that are made in the first stage. Beginning with the shortest truck route, the assignment and the routing decisions are iteratively improved. The solution times of our algorithm are compared with the solution times of the state-of-the-art formulations that are solved by CPLEX. The results demonstrate that our algorithm yields shorter solution times for the instances that we generated with the specified parameters. An optimization-based heuristic algorithm, which obtains solutions for medium-sized instances, is developed by reducing the feasible search area.     

A cooperative waiting strategy based on elliptical areas for the Dynamic Pickup and Delivery Problem with Time Windows

The purpose of this paper to present a cooperative scheduling algorithm for solving the Dynamic Pickup and Delivery Problem with Time Windows (DPDPTW). The idea behind cooperative waiting strategies is to calculate simultaneously the waiting times for all nodes in the solution. Classical non‐cooperative scheduling algorithms perform the scheduling for each route independently of the scheduling of the other routes. We present the Cooperative Scheduling Problem (CSP) based on the elliptical areas generated by vehicles waiting at their nodes. The CSP is solved by means of a genetic algorithm and is evaluated by using a set of benchmarks based on real‐life data found in the literature. Initially, two waiting strategies are presented: Wait‐Early‐Time scheduling and Balanced‐Departure scheduling. Extensive empirical simulations have been carried out by analyzing the degree of dynamism and the average waiting time, a new concept defined to take into account the gap between the time windows of pickup and delivery nodes. Copyright © 2016 John Wiley & Sons, Ltd.     

A range-restricted recharging station coverage model for drone delivery service planning

Unmanned Aerial Vehicles (UAVs) are attracting significant interest for delivery service of small packages in urban areas. The limited flight range of electric drones powered by batteries or fuel cells requires refueling or recharging stations for extending coverage to a wider area. To develop such service, optimization methods are needed for designing a network of station locations and delivery routes. Unlike ground-transportation modes, however, UAVs do not follow a fixed network but rather can fly directly through continuous space. But, paths must avoid barriers and other obstacles. In this paper, we propose a new location model to support spatially configuring a system of recharging stations for commercial drone delivery service, drawing on literature from planar-space routing, range-restricted flow-refueling location, and maximal coverage location. We present a mixed-integer programming formulation and an efficient heuristic algorithm, along with results for a large case study of Phoenix, AZ to demonstrate the effectiveness and efficiency of the model.     

The Vehicle Routing Problem: The Case of the Hong Kong Postal Service

Abstract

With the growth in population and development of business activities in Hong Kong, the range and level of services provided by Hongkong Post have multiplied. However, the schedule of its postal vehicles, including mail collection and delivery, is still constructed manually on a daily basis, based on the experience of staff and transportation reviews. In this paper, the problem of scheduling a set of n collection points (District Post Offices) from a depot (General Post Office) in Hong Kong Island is addressed. The objectives pursued are the maximization of resource utilization and minimization of operation costs. In other words, the variable cost is expected to be reduced. To achieve these goals, an integer linear programming (IP) model of the vehicle routing problem (VRP) is developed in an effort to obtain optimal solutions. As the model involves computational complexity, a commercial software package CPLEX is used to solve the problems efficiently. The results show that the proposed model can produce optimal vehicle routes and schedules.     

Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints

This paper presents new models for multiple depot vehicle scheduling problem (MDVS) and multiple depot vehicle scheduling problem with route time constraints (MDVSRTC). The route time constraints are added to the MDVS problem to account for the real world operational restrictions such as fuel consumption. Compared to existing formulations, this formulation decreases the size of the problem by about 40% without eliminating any feasible solution. It also presents an exact and two heuristic solution procedures for solving the MDVSRTC problem. Although these methods can be used to solve medium size problems in reasonable time, real world applications in large cities require that the MDVSRTC problem size be reduced. Two techniques are proposed to decrease the size of the real world problems. For real-world application, the problem of bus transit vehicle scheduling at the mass transit administration (MTA) in Baltimore is studied. The final results of model implementation are compared to the MTA's schedules in January 1998. The comparison indicates that, the proposed model improves upon the MTA schedules in all respects. The improvements are 7.9% in the number of vehicles, 4.66% in the operational time and 5.77% in the total cost.     

Just-in-time delivery for green fleets: A feedback control approach

With increasing attention being paid to greenhouse gas (GHG) emissions, the transportation industry has become an important focus of approaches to reduce GHG emissions, especially carbon dioxide equivalent (CO₂e) emissions. In this competitive industry, of course, any new emissions reduction technique must be economically attractive and contribute to good operational performance. In this paper, a continuous-variable feedback control algorithm called GEET (Greening via Energy and Emissions in Transportation) is developed; customer deliveries are assigned to a fleet of vehicles with the objective function of Just-in-Time (JIT) delivery and fuel performance metrics akin to the vehicle routing problem with soft time windows (VRPSTW). GEET simultaneously determines vehicle routing and sets cruising speeds that can be either fixed for the entire trip or varied dynamically based on anticipated performance. Dynamic models for controlling vehicle cruising speed and departure times are proposed, and the impact of cruising speed on JIT performance and fuel performance are evaluated. Allowing GEET to vary cruising speed is found to produce an average of 12.0–16.0% better performance in fuel cost, and −36.0% to +16.0% discrepancy in the overall transportation cost as compared to the Adaptive Large Neighborhood Search (ALNS) heuristic for a set of benchmark problems. GEET offers the advantage of extremely fast computational times, which is a substantial strength, especially in a dynamic transportation environment.     

The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace

The integration of drones into civil airspace is one of the most challenging problems for the automation of the controlled airspace, and the optimization of the drone route is a key step for this process. In this paper, we optimize the route planning of a drone mission that consists of departing from an airport, flying over a set of mission way points and coming back to the initial airport. We assume that during the mission a set of piloted aircraft flies in the same airspace and thus the cost of the drone route depends on the air traffic and on the avoidance maneuvers used to prevent possible conflicts. Two air traffic management techniques, i.e., routing and holding, are modeled in order to maintain a minimum separation between the drone and the piloted aircraft. The considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA), relates to the drone route planning phase and aims to minimize the total operational cost. Two heuristic algorithms are proposed for the solution of the problem. A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem, which allows holdings at mission way points, and a Branch and Cut algorithm are proposed for solving the TDTSPPCA to optimality. An additional formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and a Cutting Plane algorithm is designed. Finally, computational experiments on real-world air traffic data from Milano Linate Terminal Maneuvering Area are reported to evaluate the performance of the proposed formulations and of the heuristic algorithms.     

A new statistical method of assigning vehicles to delivery areas for CO2 emissions reduction

Transportation CO₂ emissions are expected to increase in the following decades, and thus, new and better alternatives to reduce emissions are needed. Road transport emissions are explained by different factors, such as the type of vehicle, delivery operation and driving style. Because different cities may have conditions that are characterized by diversity in landforms, congestion, driving styles, etc., the importance of assigning the proper vehicle to serve a particular region within the city provides alternatives to reduce CO₂ emissions. In this article, we propose a new methodology that results in assigning trucks to deliver in areas such that the CO₂ emissions are minimized. Our methodology clusters the delivery areas based on the performance of the vehicle fleet by using the k-means algorithm and Tukey’s method. The output is then used to define the optimal CO₂ truck-area assignment. We illustrate the proposed approach for a parcel company that operates in Mexico City and demonstrate that it is a practical alternative to reduce transportation CO₂ emissions by matching vehicle type with delivery areas.     

Reducing carbon emission of pickup and delivery using integrated scheduling

Integrated scheduling is a powerful way to reduce carbon emission of pickup and delivery because the vehicle loading efficiency can be improved. Our study investigates theoretically the potential carbon emission reduction brought by integrated scheduling, and develops the upper and lower bounds. To demonstrate the practical advantage of carbon emission reduction brought by integrated scheduling, we use the real application of pickup and delivery, i.e., “picking up and delivering customers to airport” (PDCA). Using based-on-set-partitioning formulation, we accurately obtain the minimal carbon emissions of non-integrated scheduling and integrated scheduling. We conclude that integrated scheduling reduces carbon emission by approximate 10.8%. However, the cost in integrated scheduling may be more than before, which causes a company unwilling to accept integrated scheduling. The acceptable integrated scheduling is proposed. We identify the situations under which carbon emission can be efficiently reduced in acceptable integrated scheduling based on the extensive experiments of PDCA.     

A scenario-based planning for the pickup and delivery problem with time windows,scheduled lines and stochastic demands

The Pickup and Delivery Problem with Time Windows, Scheduled Lines and Stochastic Demands (PDPTW-SLSD) concerns scheduling a set of vehicles to serve a set of requests, whose expected demands are known in distribution when planning, but are only revealed with certainty upon the vehicles’ arrival. In addition, a part of the transportation plan can be carried out on limited-capacity scheduled public transportation line services. This paper proposes a scenario-based sample average approximation approach for the PDPTW-SLSD. An adaptive large neighborhood search heuristic embedded into sample average approximation method is used to generate good-quality solutions. Computational results on instances with up to 40 requests (i.e., 80 locations) reveal that the integrated transportation networks can lead to operational cost savings of up to 16% compared with classical pickup and delivery systems.     

Modelling energy consumption of electric freight vehicles in urban pickup/delivery operations: analysis and estimation on a real-world dataset

Electric Freight Vehicles (EFVs) are a promising and increasingly popular alternative to conventional trucks in urban pickup/delivery operations. A key concerned research topic is to develop trip-based Tank-to-Wheel (TTW) analyses/models for EFVs energy consumption: notably, there are just a few studies in this area. Leveraging an earlier research on passenger electric vehicles, this paper aims at filling this gap by proposing a microscopic backward highly-resolved power-based EFVs energy consumption model (EFVs-ECM). The model is estimated and validated against real-world data, collected on a fleet of five EFVs in the city centre of Rome, for a total of 144 observed trips between subsequent pickup/delivery stops. Different model specifications are tested and contrasted, with promising results, in line with previous findings on electric passenger vehicles.     

Combining pickups and deliveries in vehicle routing – An assessment of carbon emission effects

This paper studies the effect on carbon emissions of consolidation of shipments on trucks. New positioning and communication technologies, as well as decision support systems for vehicle routing, enable better utilization of vehicle capacity, reduced travel distance, and thereby carbon emission reductions. We present a novel carbon emission analysis method that determines the emission savings obtained by an individual transport provider, who receives customer orders for outbound deliveries as well as pickup orders from supply locations. The transport provider can improve vehicle utilization by performing pickups and deliveries jointly instead of using separate trucks. In our model we assume that the transport provider minimizes costs by use of a tool that calculates detailed vehicle routing plans, i.e., an assignment of each transport order to a specific vehicle in the fleet, and the sequence of customer visit for each vehicle. We compare a basic set-up, in which pickups and deliveries are segregated and performed with separate vehicles, with two consolidation set-ups where pickups and deliveries may be mixed more or less freely on a single vehicle. By allowing mixing, the average vehicle load will increase and the total driven distance will decrease. To compare carbon emissions for the three set-ups, we use a carbon assessment method that uses the distance driven and the average load factor. An increase in the load factor can reduce part of the emission savings from consolidation. We find that emission savings are relatively large in case of small vehicles and for delivery and pickup locations that are relatively far from the depot. However, if a truck visits many demand and supply locations before returning to the depot, we observe negligible carbon emission decreases or even emission increases for consolidation set-ups, meaning that in such cases investing in consolidation through joint pickups and deliveries may not be effective. The results of our study will be useful for transport users and providers, policymakers, as well as vehicle routing technology vendors.     

The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems considering carbon dioxide emissions

Multi-echelon distribution strategy is primarily to alleviate the environmental (e.g., energy consumption and emissions) consequence of logistics operations. Differing from the long-term strategic problems (e.g., the two-echelon vehicle routing problem (2E-VRP), the two-echelon location routing problem (2E-LRP) and the truck and trailer routing problem (TTRP)) that make location decisions in depots or satellites, the paper introduces a short-term tactical problem named the two-echelon time-constrained vehicle routing problem in linehaul-delivery systems (2E-TVRP) considering carbon dioxide (CO₂) emissions. The linehaul level and the delivery level are linked through city distribution centers (CDCs). The 2E-TVRP, which takes CO₂ emissions per ton-kilometer as the objective, has inter-CDC linehaul on the 1st level and delivery from CDCs to satellites on the 2nd level. The Clarke and Wright savings heuristic algorithm (CW) improved by a local search phase is put forward. The case study shows the applicability of the model to real-life problems. The results suggest that the vehicle scheduling provided by the 2E-TVRP is promising to reduce the CO₂ emissions per ton-kilometer of the linehaul-delivery system. Adjusting the central depot location or developing the loaded-semitrailer demand among O-D pairs to eliminate empty-running of tractors will contribute to reduce the CO₂ emission factor.     

Daily newspaper distribution planning with integer programming: an application in Turkey

Abstract

This paper concerns the newspaper distribution problem. It addresses the transportation of newspapers from printing plant to newsagents with distribution vehicles under various particular constraints. The objective is to minimize the distance traveled by the vehicles and/or the number of vehicles. In this study, the routes for vehicles of a leading newspaper distributor company in the Turkish press sector are examined. The problem is defined as determining optimal delivery routes for a fleet of homogeneous vehicles, starting and ending at the printing plant that is required to serve a number of geographically dispersed newsagents with known demands under capacity and time constraints, while minimizing the total distribution cost. An integar linear programming model is proposed as a solution using Cplex. Computational results demonstrate that the proposed model is fast and able to find optimal solutions for problem scenarios with up to 55 newsagents within reasonable computing times. It was found that the proposed model reduced the delivery cost by 21% on average when compared to the current manual method. The results show that this model is adequate for medium-sized distribution problems.     

A model and optimization-based heuristic for the operational aircraft maintenance routing problem

This paper investigates the Operational Aircraft Maintenance Routing Problem (OAMRP). Given a set of flights for a specific homogeneous fleet type, this short-term planning problem requires building feasible aircraft routes that cover each flight exactly once and that satisfy maintenance requirements. Basically, these requirements enforce an aircraft to undergo a planned maintenance at a specified station before accumulating a maximum number of flying hours. This stage is significant to airline companies as it directly impacts the fleet availability, safety, and profitability. The contribution of this paper is twofold. First, we elucidate the complexity status of the OAMRP and we propose an exact mixed-integer programming model that includes a polynomial number of variables and constraints. Furthermore, we propose a graph reduction procedure and valid inequalities that aim at improving the model solvability. Second, we propose a very large-scale neighborhood search algorithm along with a procedure for computing tight lower bounds. We present the results of extensive computational experiments that were carried out on real-world flight networks and attest to the efficacy of the proposed exact and heuristic approaches. In particular, we provide evidence that the exact model delivers optimal solutions for instances with up to 354 flights and 8 aircraft, and that the heuristic approach consistently delivers high-quality solutions while requiring short CPU times.