Search

With the new distribution demands emerging continuously in the last decade, the distribution mode is changing gradually in various applications, such as e-commerce, emergency relief supplies distribution, the last-mile delivery, and so on. We formulate vehicle routing problem with pickup and delivery (VRPPD), while simultaneously considering multiple arrival time and traffic congestion constraints. Our model focuses on the clear changes of the distribution mode to meet the fast-delivery requirements in the last decade, which is characterized by the multi-batch arrival of goods in 24 hours and time-varying congestion in various time windows. Besides, we propose dynamic memory memetic algorithm, which updates its dynamic memory by whether to promote populations to find new better solutions or not. This is an effective acceleration mechanism to promote the population progress. Meanwhile, dynamic memory memetic algorithm determines the serious congestion tasks in the delivery route and transforms them into normal congestion or even non-congestion tasks. Test sets with 30 test problems are constructed by using real distribution data from Alibaba Cloud and traffic congestion data from Baidu Map in Shanghai. By comparing with four compared algorithms, the effectiveness, efficiency, and robustness of our proposed algorithm in non-congestion and congestion tests are simultaneously demonstrated.

We consider the capacitated single vehicle one-to-one pickup and delivery problem with divisible pickups and deliveries (PDPDPD). In this problem, we do not make the standard assumption of one-to-one pickup and delivery problems (PDPs) that each location has only one transportation request. Instead we assume there are multiple requests per location that may be performed individually. This may result in multiple visits to a location. We provide a new compact arc-based integer linear programming (ILP) formulation for the PDPDPD by deriving time-consistency constraints that identify the order in which selected outgoing arcs from a node are actually traversed. The formulation can also easily be applied to the one-to-one PDP by restricting the number of times that a node can be visited. Numerical results on standard one-to-one PDP test instances from the literature show that our compact formulation is almost competitive with tailor-made solution methods for the one-to-one PDP. Moreover, we observe that significant cost savings of up to 15% on average may be obtained by allowing divisible pickups and deliveries in one-to-one PDPs. It turns out that divisible pickups and deliveries are not only beneficial when the vehicle capacity is small, but also when this capacity is unrestrictive.

The rise of e-commerce has increased the demands placed on pickup and delivery operations, as well as customer expectations regarding the quality of services provided by those operations. One strategy a logistics provider can employ for meeting these increases in demands and expectations is to complement and coordinate its fleet operations with those of for-hire, third-party logistics providers. Herein, we study an optimization problem for coordinating these operations: the time-dependent profitable pickup and delivery problem with time windows. In this problem, the logistics provider has the opportunity to use its fleet of capacitated vehicles to transport shipment requests, for a profit, from pickup to delivery locations. Owing to demographic and market trends, we focus on an urban setting, wherein road congestion is a factor. As a result, the problem explicitly recognizes that travel times may be time-dependent. The logistics provider seeks to maximize its profits from serving transportation requests, which we compute as the difference between the profits associated with transported requests and transportation costs. To solve this problem, we propose an adaptive large neighborhood search algorithm. The results of our extensive computational study show that the proposed algorithm can find high-quality solutions quickly on instances with up to 75 transportation requests. Furthermore, we study its impact on profits when explicitly recognizing traffic congestion during planning operations.

One-to-one Pickup and Delivery Problem (PDP) with loading constraints is studied. Mathematical model is presented using combinatorial configurations approach for pickup and delivery and the phi-function technique for loading constraints. Two-stage solution strategy is used. The first stage has two levels: a) clustering the set of pickup and delivery points regarding to the set of vehicles and b) solving the PDP problem with 3D loading constraints for each vehicle within the appropriate cluster. The second stage improves the solution found at the previous stage and is based on the cyclic transfer approach and cyclic permutations. Computational results are presented to support efficiency of the approach.

In this paper, we study a family of time-dependent pickup and delivery problems with time windows to optimize the service of a transportation provider under two dimensions of operational flexibility. In the first, we consider problems wherein the transportation service provider can choose the transportation requests it serves in order to maximize profit. In the second, we consider problems wherein they can take advantage of periods of light traffic by dictating to drivers when their routes should begin. We also consider problems wherein these flexibilities are not present. We propose an exact solution approach for solving problems from this family that is based upon branch and price, wherein columns are generated via a tailored labeling algorithm. We augment the framework with adaptations of various speed-up techniques from the literature, including limited-memory subset-row cuts and route enumeration. With an extensive computational study, we assess the effectiveness of the proposed framework and the impact of the adapted techniques.

Inland waterway transport is becoming attractive due to its minimum environmental impact in comparison with other transportation modes. Fixed timetables and routes are adopted by most barge operators, avoiding the full utilization of the available resources. Therefore a flexible model is adopted to reduce the transportation cost and environmental impacts. This paper regards the route optimization of barges as a pickup and delivery problem (PDP). A Mixed Integer Programming (MIP) model is proposed to formulate the PDP with transshipment of barges, and an Adaptive Large Neighborhood Search (ALNS) is developed to solve the problem efficiently. The approach is evaluated based on a case study in the Rhine Alpine corridor and it is shown that ALNS is able to find good solutions in reasonable computation times. The results show that the cost is lower when there is more flexibility. Moreover, the cost comparison shows that transshipment terminals can reduce the cost for barge companies.

The pickup and delivery problem with time windows (PDPTW) is studied in this paper. It is referred to as the single-commodity capacitated vehicle routing problem with pickups and deliveries, in which a fleet of vehicles meet a group of customer demands. Each customer demand includes the usage of only one vehicle for both loading a specified quantity of one type of commodity at one place and delivering them to another place. All the demands of customers must be satisfied without exceeding the vehicle capacity and the pickup or delivery places time windows specified for each place. In this study, we introduce a novel Constraint Programming (CP) model for the PDPTW. CP is an exact solution approach that is popular for its performance to state complicated relationships and to achieve high-quality solutions within acceptable computational times for combinatorial optimization problems with complicated constraints such as the PDPTW. The performance of the proposed CP model is tested with well-known benchmark instances from literature. The results of computational analysis indicate that our CP model is very effective in finding high-quality solutions for even large size problems.

In the same-day delivery problem, requests with restricted time windows arrive during a given time horizon, and it is necessary to decide which requests to serve and how to plan routes accordingly. We solve the problem with a dynamic stochastic method that invokes a generalized route generation function combined with an adaptive large neighborhood search heuristic. The heuristic is composed of destroying and repairing operators. The generalized route generation function takes advantage of sampled-scenarios, which are solved with the heuristic, to determine which decisions should be taken at any instant. Results obtained on different benchmark instances prove the effectiveness of the proposed method in comparison with a consensus function from the literature, with an average decrease of 10.7%, in terms of solution cost, and 24.5%, in terms of runtime.

The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) consists of routing and scheduling a set of vehicles, by integrating them with scheduled public transportation lines, to serve a set of freight requests within their time windows. This paper presents an exact solution approach based on a branch-and-price algorithm. A path-based set partitioning formulation is used as the master problem, and a variant of the elementary shortest path problem with resource constraints is solved as the pricing problem. In addition, the proposed algorithm can also be used to solve the PDPTW with transfers (PDPTW-T) as a special case. Results of extensive computational experiments confirm the efficiency of the algorithm: it is able to solve small- and medium-size instances to optimality within reasonable execution time. More specifically, our algorithm solves the PDPTW-SL with up to 50 requests and the PDPTW-T with up to 40 requests on the considered instances. The online appendix is available at https://doi.org/10.1287/trsc.2017.0798 .

We introduce the time-dependent capacitated profitable tour problem with time windows and precedence constraints. This problem concerns determining a tour and its departure time at the depot that maximizes the collected profit minus the total travel cost (measured by total travel time). To deal with road congestion, travel times are considered to be time-dependent. We develop a tailored labeling algorithm to find the optimal tour. Furthermore, we introduce dominance criteria to discard unpromising labels. Our computational results demonstrate that the algorithm is capable of solving instances with up to 150 locations (75 pickup and delivery requests) to optimality. Additionally, we present a restricted dynamic programing heuristic to improve the computation time. This heuristic does not guarantee optimality, but is able to find the optimal solution for 32 instances out of the 34 instances.

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.

Common practice in crowdsourced delivery services is through direct delivery. That is by dispatching direct trip to a driver nearby the origin location. The total distance can be reduced through multiple pickup and delivery by increasing the number of requests in a trip.The research implements exact algorithm to solve the consolidation problem with up to 3 requests in a trip. Greedy heuristic is performed to construct initial route based on highest savings. The result is then optimized using Ant Colony Optimization (ACO). Four scenarios are compared. A direct delivery scenarios and three multiple pickup and delivery scenarios. These include 2-consolidated delivery, 3-consolidated delivery, and 3-consolidated delivery optimized with ACO. Four parameters are used to evaluate using Analytical Hierarchical Process (AHP). These include the number of trips, total distance, total duration, and security concerns.The case study is based on Yogyakarta area for a whole day. The final route optimized with ACO shows 178 requests can be completed in 94 trips. Compared to direct delivery, consolidation can provides savings up to 20% in distance and 14% in duration. The evaluation result using AHP shows that ACO scenario is the best scenario.

International audience; The Pickup and Delivery Problem with Shuttle routes (PDPS) is a special case of the Pickup and Delivery Problem with Time Windows (PDPTW) where the trips between the pickup points and the delivery points can be decomposed into two legs. The rst leg visits only pickup points and ends at some delivery point. The second leg is a direct trip { called a shuttle { between two delivery points. This optimization problem has practical applications in the transportation of people between a large set of pickup points and a restricted set of delivery points. This paper proposes three mathematical models for the PDPS and a branch-and-cutand- price algorithm to solve it. The pricing sub-problem, an Elementary Shortest Path Problem with Resource Constraints (ESPPRC), is solved with a labeling algorithm enhanced with e cient dominance rules. Three families of valid inequalities are used to strengthen the quality of linear relaxations. The method is evaluated on generated and real-world instances containing up to 193 transportation requests. Instances with up to 87 customers are solved to optimality within a computation time of one hour.

The Pickup and Delivery Problem with Transfers (PDPT) consists of defining a set of minimum cost routes in order to satisfy a set of transportation requests, allowing them to change vehicles at specific locations. In this problem, routes are strongly interdependent due to request transfers. Then it is critical to efficiently check if inserting a request into a partial solution is feasible or not. In this article, we present a method to perform this check in constant time.

This paper examines network design where OD demand is not known a priori, but is the subject of responses in household or user itinerary choices to infrastructure improvements. Using simple examples, we show that falsely assuming that household itineraries are not elastic can result in a lack in understanding of certain phenomena; e.g., increasing traffic even without increasing economic activity due to relaxing of space-time prism constraints, or worsening of utility despite infrastructure investments in cases where household objectives may conflict. An activity-based network design problem is proposed using the location routing problem (LRP) as inspiration. The bilevel formulation includes an upper level network design and shortest path problem while the lower level includes a set of disaggregate household itinerary optimization problems, posed as household activity pattern problem (HAPP) (or in the case with location choice, as generalized HAPP) models. As a bilevel problem with an NP-hard lower level problem, there is no algorithm for solving the model exactly. Simple numerical examples show optimality gaps of as much as 5% for a decomposition heuristic algorithm derived from the LRP. A large numerical case study based on Southern California data and setting suggest that even if infrastructure investments do not result in major changes in link investment decisions compared to a conventional model, the results provide much higher resolution temporal OD information to a decision maker. Whereas a conventional model would output the best set of links to invest given an assumed OD matrix, the proposed model can output the same best set of links, the same daily OD matrix, and a detailed temporal distribution of activity participation and travel from which changes in peak period OD patterns can be observed.