A two-stage heuristic method for vehicle routing problem with split deliveries and pickups

The vehicle routing problem （VRP） is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups （VRPSPDP） is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.     

带时间窗的同时集散货物路线问题研究

研究了业务繁忙环境下带时间窗的同时集散货物路线问题．以车辆数、运输距离和完成运输任务的总 时间最小为目标建立了多目标模型,提出用基于路线集合划分的分解迭代算法求解该问题．该算法首先用两种策略 将问题的解分解为几个子集合,用记录更新法分别求解每个子集合,将子集合求得的最好路线反馈回来形成新的当 前解,再分解迭代,逐渐改善解的质量．最后数据实验表明该算法能有效解决带时间窗的单向车辆路线问题和集散 一体化的双向车辆路线问题．     

多中心半开放式送取需求可拆分的车辆路径优化

针对多中心半开放式送取需求可拆分的车辆路径问题,构建了以车辆配送距离最短为目标的多中心半开放式送取需求可拆分的数学模型。设计大变异邻域遗传算法进行求解,采用二维染色体编码及顺序交叉策略,同时运用大变异策略和邻域搜索策略提高算法全局和局部的寻优能力,通过算例对比验证了所提模型与算法的有效性。算例实验表明,大变异邻域遗传算法在求解多中心物流配送车辆路径问题上求解质量较优、求解效率较高、求解结果较为稳定,同时验证了联合配送下多中心半开放式送取需求可拆分的配送模式优于独立配送下单中心送取需求可拆分的配送模式。研究成果不仅拓展了车辆路径问题,还可为相关快递物流企业配送优化提供决策参考。     

The vehicle routing problem with restricted mixing of deliveries and pickups

The vehicle routing problem with deliveries and pickups is one of the main problems within reverse logistics. This paper focuses on an important assumption that divides the literature on the topic, namely the restriction that all deliveries must be completed before pickups can be made. A generalised model is presented, together with a mathematical formulation and its resolution. The latter is carried out by adopting a suitable implementation of the reactive tabu search metaheuristic. Results show that significant savings can be achieved by allowing a mixture of delivery and pickup loads on-board and yet not incurring delays and driver inconvenience.     

Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery

The location routing problem with simultaneous pickup and delivery (LRPSPD) is a new variant of the location routing problem (LRP). The objective of LRPSPD is to minimize the total cost of a distribution system including vehicle traveling cost, depot opening cost, and vehicle fixed cost by locating the depots and determining the vehicle routes to simultaneously satisfy the pickup and the delivery demands of each customer. LRPSPD is NP-hard since its special case, LRP, is NP-hard. Thus, this study proposes a multi-start simulated annealing (MSA) algorithm for solving LRPSPD which incorporates multi-start hill climbing strategy into simulated annealing framework. The MSA algorithm is tested on 360 benchmark instances to verify its performance. Results indicate that the multi-start strategy can significantly enhance the performance of traditional single-start simulated annealing algorithm. Our MSA algorithm is very effective in solving LRPSPD compared to existing solution approaches. It obtained 206 best solutions out of the 360 benchmark instances, including 126 new best solutions.     

The double traveling salesman problem with multiple stacks: A variable neighborhood search approach

The double traveling salesman problem with multiple stacks (DTSPMS) is a vehicle routing problem that consists on finding the minimum total length tours in two separated networks, one for pickups and one for deliveries. A set of orders is given, each one consisting of a pickup location and a delivery location, and it is required to send an item from the former location to the latter one. Repacking is not allowed, but collected items can be packed in several rows in such a way that each row must obey the LIFO principle. In this paper, a variable neighborhood search approach using four new neighborhood structures is presented to solve the problem.     

The capacitated vehicle routing problem with stochastic demands and time windows

The capacitated vehicle routing problem with stochastic demands and time windows is an extension of the capacitated vehicle routing problem with stochastic demands, in which demands are stochastic and a time window is imposed on each vertex. A vertex failure occurring when the realized demand exceeds the vehicle capacity may trigger a chain reaction of failures on the remaining vertices in the same route, as a result of time windows. This paper models this problem as a stochastic program with recourse, and proposes an adaptive large neighborhood search heuristic for its solution. Modified Solomon benchmark instances are used in the experiments. Computational results clearly show the superiority of the proposed heuristic over an alternative solution approach.     

Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier

In this paper, we present heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem arising in a real-world situation. In this problem, customers make requests of goods, which are packed in a sortment of boxes. The objective is to find minimum cost delivery routes for a set of identical vehicles that, departing from a depot, visit all customers only once and return to the depot. Apart of the usual 3D container loading constraints which ensure that the boxes are packed completely inside the vehicles and that the boxes do not overlap each other in each vehicle, the problem also takes into account constraints related to the vertical stability of the cargo and multi-drop situations. The algorithms are based on the combination of classical heuristics from both vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include other practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. The approaches are also sufficiently generic to be embedded with algorithms other than those considered in this study, as well as they can be easily adapted to consider other practical constraints, such as the load bearing strength of the boxes, time windows and pickups and deliveries. Computational tests were performed with these methods considering instances based on the vehicle routing literature and actual customers’ orders, as well as instances based on a real-world situation of a Brazilian carrier. The results show that the heuristics are able to produce relatively good solutions for real instances with hundreds of customers and thousands of boxes.     

Artificial intelligence heuristics in solving vehicle routing problems with time window constraints

This paper describes the authors’ research on various heuristics in solving vehicle routing problem with time window constraints (VRPTW) to near optimal solutions. VRPTW is NP-hard problem and best solved to near optimum by heuristics. In the vehicle routing problem, a set of geographically dispersed customers with known demands and predefined time windows are to be served by a fleet of vehicles with limited capacity. The optimized routines for each vehicle are scheduled as to achieve the minimal total cost without violating the capacity and time window constraints. In this paper, we explore different hybridizations of artificial intelligence based techniques including simulated annealing, tabu search and genetic algorithm for better performance in VRPTW. All the implemented hybrid heuristics are applied to solve the Solomon's 56 VRPTW with 100-customer instances, and yield 23 solutions competitive to the best solutions published in literature according to the authors’ best knowledge.     

An exact method for the double TSP with multiple stacks

The double travelling salesman problem (TSP) with multiple stacks (DTSPMS) is a pickup and delivery problem in which all pickups must be completed before any deliveries can be made. The problem originates from a real‐life application where a 40‐foot container (configured as 11 rows of three columns) is used to transport 33 pallets from a set of pickup customers to a set of delivery customers. The pickups and deliveries are performed in two separate trips, where each trip starts and ends at a depot and visits a number of customers. The aim of the problem is to produce a packing plan for the pallets that minimizes the total transportation cost given that the container cannot be repacked at any stage. In this paper we present an exact solution method based on matching k‐best tours to each of the separate pickup and delivery TSPs. The approach is shown to outperform the only known previous exact method for this problem in that solutions can be obtained faster and previously unsolved instances containing as many as 18 customers can now be solved to optimality.     

A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups

A well-known variant of the vehicle routing problem involves backhauls, where vehicles deliver goods from a depot to linehaul customers and pick up goods from backhaul customers to the depot. The vehicle routing problem with divisible deliveries and pickups (VRPDDP) allows vehicles to visit each client once or twice for deliveries or pickups. In this study, a very efficient parallel approach based on variable neighborhood search (VNS) is proposed to solve VRPDDP. In this approach, asynchronous cooperation with a centralized information exchange strategy is used for parallelization of the VNS approach, called cooperative VNS (CVNS). All available problem sets of VRPDDP have been successfully solved with the CVNS, and the best solutions available in the literature have been significantly improved.     

Perturbation heuristics for the pickup and delivery traveling salesman problem

This article describes and compares seven perturbation heuristics for the Pickup and Delivery Traveling Salesman Problem (PDTSP). In this problem, a shortest Hamiltonian cycle is sought through a depot and several pickup and delivery pairs. Perturbation heuristics are diversification schemes which help a local search process move away from a local optimum. Three such schemes have been implemented and compared: Instance Perturbation, Algorithmic Perturbation, and Solution Perturbation. Computational results on PDTSP instances indicate that the latter scheme yields the best results. On instances for which the optimum is known, it consistently produces optimal or near-optimal solutions.Scope and purposeIn several distribution management contexts, it is necessary to construct a shortest tour starting at a depot and making several pickup and deliveries. In the Traveling Salesman Problem with Pickup and Delivery, to each pickup point is associated a delivery point later in the tour. Like several routing problems, the PDTSP is very hard to solve to optimality and local search heuristics often get trapped in local optima. Perturbation heuristics provide a means of escaping from local optima. This paper describes and compares three types of perturbation heuristic. It shows that the best scheme consistently yields high-quality solutions.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.     

The traveling purchaser problem,with multiple stacks and deliveries: A branch-and-cut approach

The Double Traveling Salesman Problem with Multiple Stacks is a pickup-and-delivery single-vehicle routing problem which performs all pickup operations before the deliveries. The vehicle has a loading space divided into stacks of a fixed height that follows a Last-In-First-Out policy. It has to collect products following a Hamiltonian tour in a pickup region, and then deliver them following a Hamiltonian tour in a delivery region. The aim is to minimize the total routing cost while satisfying the vehicle loading constraints.     

A memetic algorithm for the capacitated location-routing problem with mixed backhauls

The design of distribution networks is one of the most important problems in supply chain and logistics management. The main elements in designing a distribution network are location and routing decisions. As these elements are interdependent in many distribution networks, the overall system cost can decrease if location and routing decisions are simultaneously tackled. In this paper, we consider a Capacitated Location-Routing Problem with Mixed Backhauls (CLRPMB) which is a general case of the capacitated location-routing problem. CLRPMB is defined as finding locations of the depots and designing vehicle routes in such a way that pickup and delivery demands of each customer must be performed with the same vehicle and the overall cost is minimized. Since CLRPMB is an NP-hard problem, we propose a memetic algorithm to solve the problem. To evaluate the performance of the proposed approach, we conduct an experimental study and compare its results with the lower bounds obtained by the branch-and-cut algorithm on a set of instances derived from the literature. Computational results indicate that the proposed approach is able to find optimal or very good quality solutions in a reasonable computation time.     

Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows

In this paper a model and several solution procedures for a novel type of vehicle routing problems where time windows for the pickup of perishable goods depend on the dispatching policy used in the solution process are presented. This problem is referred to as Vehicle Routing Problem with multiple interdependent time windows (VRPmiTW) and is motivated by a project carried out with the Austrian Red Cross blood program to assist their logistics department. Several variants of a heuristic constructive procedure as well as a branch-and-bound based algorithm for this problem were developed and implemented. Besides finding the expected reduction in costs when compared with the current procedures of the Austrian Red Cross, the results show that the heuristic algorithms find solutions reasonably close to the optimum in fractions of a second. Another important finding is that increasing the number of pickups at selected customers beyond the theoretical minimum number of pickups yields significantly greater potential for cost reductions.     

Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem

The paper addresses the problem of multi-depot vehicle routing in order to minimize the delivery time of vehicle objective. Three hybrid heuristics are presented to solve the multi-depot vehicle routing problem. Each hybrid heuristic combines elements from both constructive heuristic search and improvement techniques. The improvement techniques are deterministic, stochastic and simulated annealing (SA) methods. Experiments are run on a number of randomly generated test problems of varying depots and customer sizes. Our heuristics are shown to outperform one of the best-known existing heuristic. Statistical tests of significance are performed to substantiate the claims of improvement.     

Heuristics for a multiperiod inventory routing problem with production decisions

Manufacturers who resupply a large number of retailers on a periodic basis continually struggle with the question of how to formulate a replenishment strategy. This paper presents a comparative analysis of a series of heuristics for an inventory routing problem (IRP) that arises in a manufacturing supply chain. The IRP is formulated as a mixed integer program with the objective of maximizing the net benefits associated with making deliveries in a specific time period to a widely dispersed set of customers. It is assumed that inventory can accumulate at the customer sites, but that all demand must be met without backlogging. Because optimal solutions were not within reach of exact methods, a two-step procedure was developed that first estimates daily delivery quantities and then solves a vehicle routing problem for each day of the planning horizon. As part of the methodology, a linear program is used to determine which days it is necessary to make at least some deliveries to avoid stockouts.The IRP is investigated in the context of an integrated production–inventory–distribution–routing problem (PIDRP). The full model takes into account production decisions and inventory flow balance in each period. For the computations, a previously developed branch-and-price algorithm is used that requires the solution of multiple IRPs (one in each period) to generate columns for the master problem. Testing showed that PIDRP instances with up to eight time periods and 50 customers can be solved within 1 h. This level of performance could not be matched by either CPLEX or an exact version of the branch-and-price algorithm.     

Solving the multi-compartment capacitated location routing problem with pickup–delivery routes and stochastic demands

This paper considers an advanced capacitated location routing problem in a distribution network with multiple pickup and delivery routes, and each customer placing random multi-item demands on it. The pickup and delivery services need two fleets of vehicles and will form two different sets of routes. However, the unpredictability of variation in the multi-item demands makes the routing of multi-compartment vehicles to accommodate such demands complex. To solve this multifaceted problem, a new process employing the TABU search is proposed in this research study. This proposed approach includes three stages: location selection, customer assignment, and vehicle routing. The innovative concept is to divide all customers into assignment-determined and assignment-undetermined groups in order to narrow down the search area of a solution domain so the TABU search can be more efficient and effective. Two sets of benchmarks are then generated to verify the quality of the proposed method. According to the experiment results, the proposed solution process can both resolve the problems and yield good results in a reasonable amount of computing time. The analysis of the solution process parameters is also provided. In addition, the comparisons between stochastic demand and deterministic demand cases are calculated and discussed as well.     

A heuristic method for the vehicle routing problem with mixed deliveries and pickups

The vehicle routing problem with deliveries and pickups is a challenging extension to the vehicle routing problem that lately attracted growing attention in the literature. This paper investigates the relationship between two versions of this problem, called “mixed” and “simultaneous”. In particular, we wish to know whether a solution algorithm designed for the simultaneous case can solve the mixed case. To this end, we implement a metaheuristic based on reactive tabu search. The results suggest that this approach can yield good results.