A Multi-Trip Split-Delivery Vehicle Routing Problem with Time Windows for Inventory Replenishment Under Stochastic Travel Times

This study considers a multi-trip split-delivery vehicle routing problem with soft time windows for daily inventory replenishment under stochastic travel times. Considering uncertainty in travel times for vehicle routing problems is beneficial because more robust schedules can be generated and unanticipated consequences can be reduced when schedules are implemented in reality. However, uncertainties in model parameters have rarely been addressed for the problems in this category mainly due to the high problem complexity. In this study, an innovative and practical approach is proposed to consider stochastic travel times in the planning process. In the planning model, the possible outcomes of vehicle arrivals and product delivery at retailers are systematically categorized and their associated penalty and reward are estimated. Thus, unanticipated costs for every scheduling decision can be incorporated into the planning model to generate vehicle routing schedules that are more robust facing uncertain traffic conditions. To solve the model that is characterized as an NP-hard problem in a reasonable amount of time, a two-stage heuristic solution algorithm is proposed. Finally, the stochastic model is compared with the deterministic model in both planning and simulated operation stages using the data of a supply chain in Taiwan. The result confirms that the schedule generated by the stochastic model is more robust than the one created with the deterministic model because undesired outcomes such as unfulfilled demands are greatly reduced.     

A decomposition-based heuristic for stochastic emergency routing problems

This paper proposes a decomposition-based heuristic for a network delivery problem in which relief workers acquire valuable emergency supplies from relief warehouses, and transport them to meet the urgent needs of distressed population centres. The problem context dictates that the relief items reach these population centres before critical deadlines. However, co-ordination challenges and random disruptions introduce uncertainty in both network travel times and the destination deadlines. Hence, relief workers have to negotiate the tension between ensuring a high probability of punctual delivery and maximising the combined value of the relief supplies delivered. For an arbitrary routing scheme which guarantees punctual delivery in an uncertainty-free state of nature, the heuristic yields an upper bound on the probability that, under uncertainty, the routing scheme described will lead to tardy delivery. We demonstrate our solution approach on a small numerical example and glean insights from experiments on a realistically sized problem. Overall, our central model and proposed solution approach are useful to managers who need to evaluate routing options and devise effective operational delivery plans in humanitarian crisis situations.     

Network service scheduling and routing

Real‐life vehicle routing problems generally have both routing and scheduling aspects to consider. Although this fact is well acknowledged, few heuristic methods exist that address both these complicated aspects simultaneously. We present a graph theoretic heuristic to determine an efficient service route for a single service vehicle through a transportation network that requires a subset of its edges to be serviced, each a specified (potentially different) number of times. The times at which each of these edges are to be serviced should additionally be as evenly spaced over the scheduling time window as possible, thus introducing a scheduling consideration to the problem. Our heuristic is based on the tabu search method, used in conjunction with various well‐known graph theoretic algorithms, such as those of Floyd (for determining shortest routes) and Frederickson (for solving the rural postman problem). This heuristic forms the backbone of a decision support system that prompts the user for certain parameters from the physical situation (such as the service frequencies and travel times for each network link as well as bounds in terms of acceptability of results) after which a service routing schedule is suggested as output. The decision support system is applied to a special case study, where a service routing schedule is sought for the South African national railway system by Spoornet (the semi‐privatised South African national railways authority and service provider) as part of their rationalisation effort, in order to remain a lucrative company.     

An effective heuristic for solving a combined cargo and inventory routing problem in tramp shipping

In this paper a vendor managed inventory (VMI) service in tramp shipping is considered. VMI takes advantage of introducing flexibility in delivery time and cargo quantities by transferring inventory management and ordering responsibilities to the vendor which in this case is a shipping company. A two-phase heuristic is proposed to determine routes and schedules for the shipping company. The heuristic first converts inventories into cargoes, thus turning the problem into a classic ship routing and scheduling problem. It then uses adaptive large neighborhood search to solve the resulting cargo routing and scheduling problem. The heuristic iteratively changes the cargoes generated to handle the customer’s inventories, based on the information obtained from an initial solution. Computational results are presented, discussed and compared with exact solutions on large realistic instances. The results reveal the potential savings from converting traditional contracts of affreightment to an integrated VMI service. The factors that influence the benefits obtainable through VMI are also analyzed.     

Vehicle routing and scheduling with dynamic travel times

The field of dynamic vehicle routing and scheduling is growing at a fast pace nowadays, due to many potential applications in courier services, emergency services, truckload and less-than-truckload trucking, and many others. In this paper, a dynamic vehicle routing and scheduling problem with time windows is described where both real-time customer requests and dynamic travel times are considered. Different reactive dispatching strategies are defined and compared through the setting of a single “tolerance” parameter. The results show that some tolerance to deviations with the current planned solution usually leads to better solutions.     

Multicriteria pickup and delivery problem with transfer opportunity

In this research, we develop a multiobjective vehicle routing and scheduling heuristic for a pickup and delivery problem. The problem contains time window, advanced request, multi-vehicle and many-to-many transport. In addition, the fleet size is not predetermined, and customers are allowed to transfer between vehicles. The objectives of scheduling are to minimize vehicle expense, tardiness and travel time. We propose a concurrent scheduling approach, which allocates customers to more than one vehicle and assigns more than one customer to a vehicle at a time. It differs from the usual concurrent approach in three aspects: (i) it uses the look-ahead strategy to construct miniroute; (ii) it adopts the head/tail, head, and tail integration techniques; and (iii) it allows interactivity. The procedure takes full advantage of due time and travel time information and is implemented through a computer program. It is a one-phase heuristic that can be reiterated when necessary. We provide detailed programming procedures and present the computational results of the proposed algorithm through the real data.     

Heuristics for the robust vehicle routing problem with time windows

Uncertainty is frequently present in logistics and transportation, where vehicle routing problems play a crucial role. However, due to the complexity inherent in dealing with uncertainty, most research has been devoted to deterministic problems. This paper considers a robust version of the vehicle routing problem with hard time windows, in which travel times are uncertain. A budget polytope uncertainty set describes the travel times, to limit the maximum number of sailing legs that can be delayed. This makes sure that improbable scenarios are not considered, while making sure that solutions are immune to delays on a given number of sailing legs. Existing exact methods are only able to solve small instances of the problem and can be computationally demanding. With the aim of solving large instances with reduced running times, this paper proposes an efficient heuristic based on adaptive large neighborhood search. The computational study performed on instances with different uncertainty levels compares and analyzes the performance of four versions of the heuristic and shows how good quality solutions can be obtained within short computational times.     

Travel Time Reliability in Vehicle Routing and Scheduling with Time Windows

This paper presents calibration of the Vehicle Routing and scheduling Problems with Time Windows-Probabilistic (VRPTW-P) model which takes into account the uncertainty of travel times. Probe vehicle data of travel times were obtained from usual operation of pickup-delivery trucks in South Osaka area. The optimal solution of the VRPTW-P model resulted in reducing total cost, running times and CO₂, NOx and Particle Materials (PM) emissions compared with the usual operation. This is attributed to better routing of VRPTW-P to choose more reliable roads. Therefore, VRPTW-P can contribute to establish efficient and environmentally friendly delivery systems in urban area.     

Online vehicle routing and scheduling with dynamic travel times

The developments in mobile communication technologies are a strong motivation for the study of dynamic vehicle routing and scheduling problems. In particular, the planned routes can be quickly modified to account for the occurrence of new customer requests, which might imply diverting a vehicle away from its current destination. In this paper, a previously developed problem-solving approach for a vehicle routing problem with dynamic requests and dynamic travel times is extended to account for more sophisticated communication means between the drivers and the central dispatch office. Computational results are reported to empirically demonstrate the benefits of this extension.     

Solving fuzzy capacitated location routing problem using hybrid variable neighborhood search and evolutionary local search

A fuzzy capacitated location routing problem (FCLRP) is solved by using a heuristic method that combines variable neighborhood search (VNS) and evolutionary local search (ELS). Demands of the customer and travel times between customers and depots are considered as fuzzy and deterministic variables, respectively in FCLRP. Heterogeneous and homogeneous fleet sizes are performed together to reach the least multi-objective cost in a case study. The multi-objective cost consists of transportation cost, additional cost, vehicle waiting cost and delay cost. A fuzzy chance constrained programming model is added by using credibility theory. The proposed method reaches the solution by performing four stages. In the first stage, initial solutions are obtained by using a greedy heuristic method, and then VNS heuristic, which consists of seven different neighborhood structures, is performed to improve the solution quality in the second stage. In the third stage, a perturbation procedure is applied to the improved solution using ELS algorithm, and then VNS heuristic is applied again in the last stage. The combination of VNS and ELS is called VNSxELS algorithm and applied to a case study, which has fifty-seven customers and five distributing points, effectively in a reasonable time.     

A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service

On-time shipment delivery is critical for just-in-time production and quick response logistics. Due to uncertainties in travel and service times, on-time arrival probability of vehicles at customer locations can not be ensured. Therefore, on-time shipment delivery is a challenging job for carriers in congested road networks. In this paper, such on-time shipment delivery problems are formulated as a stochastic vehicle routing problem with soft time windows under travel and service time uncertainties. A new stochastic programming model is proposed to minimize carrier’s total cost, while guaranteeing a minimum on-time arrival probability at each customer location. The aim of this model is to find a good trade-off between carrier’s total cost and customer service level. To solve the proposed model, an iterated tabu search heuristic algorithm was developed, incorporating a route reduction mechanism. A discrete approximation method is proposed for generating arrival time distributions of vehicles in the presence of time windows. Several numerical examples were conducted to demonstrate the applicability of the proposed model and solution algorithm.     

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.     

Hyperpath-based vehicle routing and scheduling method in time-varying networks for airport shuttle service

It is very significant for a reasonable vehicle routing and scheduling in city airport shuttle service to decrease operational costs and increase passenger satisfaction. Most of the existing reports for such problems assumed that the travel time was invariable. However, the ever-increasing traffic congestion often makes it variable. In this study, considering the time-varying networks, a vehicle routing and scheduling method is proposed, where the time-varying feature enables the traveler to select a direction among all the Pareto-optimal paths at each node in response to the knowledge of the time window demands. Such Pareto-optimal paths are referred to hyperpaths herein. To obtain the hyperpaths, an exact algorithm is designed in this study for addressing the bi-criteria shortest paths problem, where the travel time comes to be discontinuous time-varying. Given the techniques that generate all Pareto-optimal solutions exhibiting exponential worst-case computational complexity, embedded in the exact algorithm, a computationally efficient bound strategy is reported on the basis of passenger locations, pickup time windows and arrival time windows. As such, the vehicle routing and scheduling problem viewed as an arc selection model can be solved by a proposed heuristic algorithm combined with a dynamic programming method. A series of experiments by using the practical pickup data indicate that the proposed methods can obtain cost-saving schedules under the condition of time-varying travel times.

     

基于混合元启发式算法的订单分批问题

订单拣选是仓库运营管理中一项高劳动强度与高成本的操作,拣货员在仓库中从货位拣选出满足订单需求的货物.订单分批问题(order batching problem, OBP)是订单拣选中的重要规划问题,该问题以最小化拣选批次路径时长为目标,将用户订单分配至拣选批次中.首先,为了优化订单分配构造高质量批次,提出一种混合元启发式算法,在自适应大邻域搜索框架中融入基于不可行下降的局部搜索,同时引入自适应惩罚机制和一批基于订单与基于批次的移除启发式以及新的算法组件;其次,为了优化拣选路径进一步降低批次旅行时间,提出单向启发式,利用动态规划优化组合多个路径策略.实验表明,在合理计算时间内,所提出算法的求解质量优于多重启变邻域搜索(MS-VNS)、混合自适应大邻域搜索及禁忌搜索(ALNS/TS),而且所提出算法的最大路径长度减少率达到22.36%.     

Restricted dynamic programming: A flexible framework for solving realistic VRPs

Most successful solution methods for solving large vehicle routing and scheduling problems are based on local search. These approaches are designed and optimized for specific types of vehicle routing problems (VRPs). VRPs appearing in practice typically accommodate restrictions that are not accommodated in classical VRP models, such as time-dependent travel times and driving hours regulations. We present a new construction framework for solving VRPs that can handle a wide range of different types of VRPs. In addition, this framework accommodates various restrictions that are not considered in classical vehicle routing models, but that regularly appear in practice. Within this framework, restricted dynamic programming is applied to the VRP through the giant-tour representation. This algorithm is a construction heuristic which for many types of restrictions and objective functions leads to an optimal algorithm when applied in an unrestricted way. We demonstrate the flexibility of the framework for various restrictions appearing in practice. The computational experiments demonstrate that the framework competes with state of the art local search methods when more realistic constraints are considered than in classical VRPs. Therefore, this new framework for solving VRPs is a promising approach for practical applications.     

The dynamic multi-period vehicle routing problem

This paper considers the dynamic multi-period vehicle routing problem which deals with the distribution of orders from a depot to a set of customers over a multi-period time horizon. Customer orders and their feasible service periods are dynamically revealed over time. The objectives are to minimize total travel costs and customer waiting, and to balance the daily workload over the planning horizon. This problem originates from a large distributor operating in Sweden. It is modeled as a mixed integer linear program, and solved by means of a three-phase heuristic that works over a rolling planning horizon. The multi-objective aspect of the problem is handled through a scalar technique approach. Computational results show that the proposed approach can yield high quality solutions within reasonable running times.     

A novel two-phase heuristic method for vehicle routing problem with backhauls

This paper raises a novel two-phase heuristic method to solve vehicle routing problems with backhauls. Differing from other vehicle routing problems, we consider the travel speed of vehicle to be time dependent, which will be used for the model of rush hour in an urban city. In the first phase, the original solution is generated by extending traditional heuristic methods and in the second phase, the reactive tabu search algorithm is used to optimize the original solution. We verified that this algorithm is efficient in a number of standard test cases. After comparison with the closest neighboring search algorithm, we found that the results of two-phase heuristic methods are more reasonable.     

Vehicle routing scheduling for cross-docking in the supply chain

One of the most important factors in implementing supply chain management is to efficiently control the physical flow of the supply chain. Due to its importance, many companies are trying to develop efficient methods to increase customer satisfaction and reduce costs. In various methods, cross-docking is considered a good method to reduce inventory and improve responsiveness to various customer demands. However, previous studies have dealt mostly with the conceptual advantages of cross-docking or actual issues from the strategic viewpoint. It is also necessary, however, to considering cross-docking from an operational viewpoint in order to find the optimal vehicle routing schedule. Thus, an integrated model considering both cross-docking and vehicle routing scheduling is treated in this study. Since this problem is known as NP-hard, a heuristic algorithm based on a tabu search algorithm is proposed. In the numerical example, our proposed algorithm found a good solution whose average percentage error was less than 5% within a reasonable amount of time.     

A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. This problem has been addressed using many different techniques including both exact and heuristic methods. The VRPTW benchmark problems of Solomon [Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 1987; 35(2): 254–65] have been most commonly chosen to evaluate and compare all algorithms. Results from exact methods have been improved considerably because of parallel implementations and modern branch-and-cut techniques. However, 24 out of the 56 high order instances from Solomon's original test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many of the heuristic methods developed have proved to be efficient in identifying good solutions in reasonable amounts of time. Unfortunately, whilst the research efforts based on exact methods have been focused on the total travel distance, the focus of almost all heuristic attempts has been on the number of vehicles. Consequently, it is more difficult to compare and take advantage of the strong points from each approach. This paper proposes a robust heuristic approach for the VRPTW using travel distance as the main objective through an efficient genetic algorithm and a set partitioning formulation. The tests were produced using real numbers and truncated data type, allowing a direct comparison of its results against previously published heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previously known and published heuristic methods in terms of the minimal travel distance.     

A GRASP approach to transporter scheduling and routing at a shipyard

We address the transporter scheduling and routing problem at a shipyard, which can be transformed into parallel machine scheduling with sequence-dependent setup times and precedence constraints. The objective is to maximize the workload balance among transporters under the time constraint that all assembly blocks should be transported in the predetermined period. We develop the GRASP algorithm for transporter scheduling and routing. Through simulation experiments we analyze some aspects of the developed GRASP algorithm and verify the performance of the developed GRASP algorithm. The comparison experiments show that the developed GRASP algorithm is a promising heuristic for transporter scheduling and routing.