A multilevel approach for modelling vehicle routing problem with uncertain travelling time

Vehicle routing problem is concerned with finding optimal collection or delivery routes in a transportation network, beginning and ending at a central depot, for a fleet of vehicles to serve a set of customers under some constraints. Assuming the travel times between two customers are uncertain variables, this paper proposes an uncertain multilevel programming model for a vehicle routing problem, of which the leader’s object is to minimize the total waiting times of the customers, and the followers’ objects are to minimize the waiting times of the vehicles for the beginning moments of the customers’ time windows. The uncertain multilevel programming model is transformed into a determinacy programming model, and an intelligent algorithm is designed for solving the crisp model.     

An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen

The vehicle routing problem with time windows and multiple deliverymen (VRPTWMD) is a variant of the vehicle routing problem with time windows in which service times at customers depend on the number of deliverymen assigned to the route that serves them. In particular, a larger number of deliverymen in a route leads to shorter service times. Hence, in addition to the usual routing and scheduling decisions, the crew size for each route is also an endogenous decision. This problem is commonly faced by companies that deliver goods to customers located in busy urban areas, a situation that requires nearby customers to be grouped in advance so that the deliverymen can serve all customers in a group during one vehicle stop. Consequently, service times can be relatively long compared to travel times, which complicates serving all scheduled customers during regular work hours. In this paper, we propose a hybrid method for the VRPTWMD, combining a branch-price-and-cut (BPC) algorithm with two metaheuristic approaches. We present a wide variety of computational results showing that the proposed hybrid approach outperforms the BPC algorithm used as standalone method in terms of both solution quality and running time, in some classes of problem instances from the literature. These results indicate the advantages of using specific algorithms to generate good feasible solutions within an exact method.     

行驶时间和服务时间随机的集配货一体的分批配送车辆路径优化

将铁路物流中心集配货路径问题抽象为行驶时间和服务时间随机的集送货一体的分批配送车辆路径问题进行优化.根据问题特点建立带修正的随机规划模型,对迭代局部搜索算法进行改进,设计允许分批配送的初始解构造算法、局部搜索算法和扰动机制.算例测试证实:分批配送在中等规模和大规模算例中能发挥较好的作用,大部分中等规模和大规模算例都比不允许分批配送时所得到的解更优,部分中等规模和大规模算例车辆数有所减少;配送点数随着算例规模的扩大而增加,但是配送点数占顾客点数的比例却逐步降低;随机因素随机性增加将导致目标函数增大,对分批配送点数的影响不大.     

平衡装载约束下的车辆路径问题研究

针对车辆三维装载约束下的车辆路径问题（3L-VRP）进行研究,引进车辆的平衡装载约束,综合考虑传统的先进后出、局部支撑、脆弱性等约束,构建平衡装载约束下的车辆路径问题（BL-VRP）模型。针对模型中的平衡约束,提出一种接触面积的装载算法。在此基础上,构建以回溯遗传算法（B-GA）为骨架的多阶段算法框架,对车辆路径优化进行求解。研究结果表明,多阶段算法不仅在解决3L-VRP上好于目前已有算法,同时对BL-VRP表现优秀。提出的多阶段算法为解决BL-VRP问题提供一条参考思路,但在时效性上需要进一步完善。     

考虑客户分类的随机时间车辆路径优化模型与算法

针对一类考虑客户分类、随机旅行时间、随机服务时间及时间窗约束的车辆路径问题构建了机会约束规划模型,该模型考虑两类客户（普通客户与优质客户）并通过添加机会约束条件确保优质客户获得准时服务的概率。同时,设计了变邻域迭代局部搜索算法,并给出了一种基于最小等待时间的初始解生成启发式规则。基于Solomon算例进行了多组仿真实验。仿真实验结果表明,所设计生成初始解的启发式规则是有效的;所给算法能够在短时间内找到确定问题和随机问题的近似最优解;客户比与车辆使用数目呈正相关关系。研究结果对解决资源有限条件下克服随机不确定性因素带来的不利影响、保证客户服务水平等问题有一定的参考意义。     

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 Novel Model for the Time Dependent Competitive Vehicle Routing Problem: Modified Random Topology Particle Swarm Optimization

This paper presents a novel model for a time dependent vehicle routing problem when there is a competition between distribution companies for obtaining more sales. In a real-world situation many factors cause the time dependency of travel times, for example traffic condition on peak hours plays an essential role in outcomes of the planned schedule in urban areas. This problem is named as “Time dependent competitive vehicle routing problem” (TDVRPC) which a model is presented to satisfy the “non-passing” property. The main objectives are to minimize the travel cost and maximize the sale in order to serve customers before other rival distributors. To solve the problem, a Modified Random Topology Particle Swarm Optimization algorithm (RT-PSO) is proposed and the results are compared with branch and bound algorithm in small size problems. In large scales, comparison is done with original PSO. The results show the capability of the proposed RT-PSO method for handling this problem.     

Very large-scale vehicle routing: new test problems,algorithms, and results

The standard vehicle routing problem was introduced in the OR/MS literature about 45 years ago. Since then, the vehicle routing problem has attracted an enormous amount of research attention. In the late 1990s, large vehicle routing problem instances with nearly 500 customers were generated and solved using metaheuristics. In this paper, we focus on very large vehicle routing problems. Our contributions are threefold. First, we present problem instances with as many as 1200 customers along with estimated solutions. Second, we introduce the variable-length neighbor list as a tool to reduce the number of unproductive computations. Third, we apply record-to-record travel with a variable-length neighbor list to 32 problem instances and obtain high-quality solutions, very quickly.     

Optimal Information Location for Adaptive Routing

One strategy for addressing uncertain roadway conditions and travel times is to provide real-time travel information to drivers through variable message signs, highway advisory radio, or other means. However, providing such information is often costly, and decisions must be made about the most useful places to inform drivers about local conditions. This paper addresses this question, building on adaptive routing algorithms describing optimal traveler behavior in stochastic networks with en route information. Three specific problem contexts are formulated: routing of a single vehicle, assignment of multiple vehicles in an uncongested network, and adaptive equilibrium with congestion. A network contraction procedure is described which makes an enumerative algorithm computationally feasible for small-to-medium sized roadway networks, along with heuristics which can be applied for large-scale networks. These algorithms are demonstrated on three networks of varying size.     

A dynamic vehicle routing problem with time-dependent travel times

In this paper we present a formulation for the dynamic vehicle routing problem with time-dependent travel times. We also present a genetic algorithm to solve the problem. The problem is a pick-up or delivery vehicle routing problem with soft time windows in which we consider multiple vehicles with different capacities, real-time service requests, and real-time variations in travel times between demand nodes.The performance of the genetic algorithm is evaluated by comparing its results with exact solutions and lower bounds for randomly generated test problems. For small size problems with up to 10 demands, the genetic algorithm provides almost the same results as the exact solutions, while its computation time is less than 10% of the time required to produce the exact solutions. For the problems with 30 demand nodes, the genetic algorithm results have less than 8% gap with lower bounds.This research also shows that as the uncertainty in the travel time information increases, a dynamic routing strategy that takes the real-time traffic information into account becomes increasingly superior to a static one. This is clear when we compare the static and dynamic routing strategies in problem scenarios that have different levels of uncertainty in travel time information. In additional tests on a simulated network, the proposed algorithm works well in dealing with situations in which accidents cause significant congestion in some part of the transportation network.     

Decremental algorithm for adaptive routing incorporating traveler information

Routing in a stochastic and dynamic (time-dependent) network is a crucial transportation problem. A new variant of adaptive routing, which assumes perfect online information of continuous real-time link travel time, is proposed. Driver's speed profile is taken into consideration to realistically estimate travel times, which also involves the stochasticity of links in a dynamic network. An adaptive approach is suggested to tackle the continuous dynamic shortest path problem. A decremental algorithm is consequently developed to reduce optimization time. The impact of the proposed adaptive routing and the performance of the decremental approach are evaluated in static and dynamic networks under different traffic conditions. The proposed approach can be incorporated into vehicle navigation systems.     

Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem

The vehicle routing problem (VRP) has been addressed in many research papers. Only a few of them take time-dependent travel speeds into consideration. Moreover, most research related to the VRP aims to minimize total travel time or travel distance. In recent years, reducing carbon emissions has become an important issue. Therefore, fuel consumption is also an important index in the VRP. In this research a model is proposed for calculating total fuel consumption for the time-dependent vehicle routing problem (TDVRP) where speed and travel times are assumed to depend on the time of travel when planning vehicle routing. In the model, the fuel consumption not only takes loading weight into consideration but also satisfies the “non-passing” property, which is ignored in most TDVRP-related research papers. Then a simulated annealing (SA) algorithm is proposed for finding the vehicle routing with the lowest total fuel consumption. An experimental evaluation of the proposed method is performed. The results show that the proposed method provides a 24.61% improvement in fuel consumption over the method based on minimizing transportation time and a 22.69% improvement over the method based on minimizing transportation distances.     

A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands

The multi-compartment vehicle routing problem (MC-VRP) consists of designing transportation routes to satisfy the demands of a set of customers for several products that, because of incompatibility constraints, must be loaded in independent vehicle compartments. Despite its wide practical applicability the MC-VRP has not received much attention in the literature, and the few existing methods assume perfect knowledge of the customer demands, regardless of their stochastic nature. This paper extends the MC-VRP by introducing uncertainty on what it is known as the MC-VRP with stochastic demands (MC-VRPSD). The MC-VRPSD is modeled as a stochastic program with recourse and solved by means of a memetic algorithm. The proposed memetic algorithm couples genetic operators and local search procedures proven to be effective on deterministic routing problems with a novel individual evaluation and reparation strategy that accounts for the stochastic nature of the problem. The algorithm was tested on instances of up to 484 customers, and its results were compared to those obtained by a savings-based heuristic and a memetic algorithm (MA/SCS) for the MC-VRP that uses a spare capacity strategy to handle demand fluctuations. In addition to effectively solve the MC-VRPSD, the proposed MA/SCS also improved 14 best known solutions in a 40-problem testbed for the MC-VRP.     

A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries

The vehicle routing problem with simultaneous pick-up and deliveries, which considers simultaneous distribution and collection of goods to/from customers, is an extension of the capacitated vehicle routing problem. There are various real cases, where fleet of vehicles originated in a depot serves customers with pick-up and deliveries from/to their locations. Increasing importance of reverse logistics activities make it necessary to determine efficient and effective vehicle routes for simultaneous pick-up and delivery activities. The vehicle routing problem with simultaneous pick-up and deliveries is also NP-hard as a capacitated vehicle routing problem and this study proposes a genetic algorithm based approach to this problem. Computational example is presented with parameter settings in order to illustrate the proposed approach. Moreover, performance of the proposed approach is evaluated by solving several test problems.     

Vehicle routing problem with stochastic travel times including soft time windows and service costs

This paper studies a vehicle routing problem with soft time windows and stochastic travel times. A model is developed that considers both transportation costs (total distance traveled, number of vehicles used and drivers' total expected overtime) and service costs (early and late arrivals). We propose a Tabu Search method to solve this model. An initialization algorithm is developed to construct feasible routes by taking into account the travel time stochasticity. Solutions provided by the Tabu Search algorithm are further improved by a post-optimization method. We conduct our computational experiments for well-known problem instances. Results show that our Tabu Search method performs well by obtaining very good final solutions in a reasonable amount of time.     

一种求解两级车辆路径问题的Memetic 算法

两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第1级),再由中转站配送至客户(第2级)的一种车辆路径问题。针对该NP难问题提出一种Memetic算法通过自底向上的方式进行求解。首先利用改进的最优切割算法MDVRP-Split将客户合理分配至中转站;然后采用局部搜索解决第1级问题,交叉产生的精英个体通过局部搜索改进。标准算例的测试结果表明,所提出算法更注重求解质量与求解效率的平衡,性能优于其他现有的两种算法。     

嵌套分割算法在随机需求车辆路径问题中的应用研究

对需求量满足二项分布的随机需求车辆路径问题进行了研究,在服务失败时采取允许部分服务的策略,并将嵌套分割算法与扫描算法相结合,给出了一种新的求解随机需求车辆路径问题的两阶段算法,数值试验验证了该算法的有效性。同时,该算法也拓展了车辆路径问题的算法空间。     

Traveling salesman problems with profits and stochastic customers

In this paper, we introduce a class of new selection and routing problems, and name it as the traveling salesman problem with profits and stochastic customers (TSPPSC), which is an extension of the traveling salesman problem with profits (TSPP). The class of new problems is put forward to address how to deal with stochastic customer presence under the environment in which an associated profit is obtained once a customer is visited. It is defined on a complete graph in which profits are associated with the vertices and travel costs are associated with the edges. Each vertex (customer) has a probability of requiring a visit. The objective is the simultaneous optimization of the expected collected profits and expected travel costs. According to the way the two objectives (profits and travel costs) are addressed, TSPPSC is categorized into three subproblems. Mathematical formulations are provided for these problems and a genetic algorithm is proposed to solve one of these subproblems. Computational experiments conducted on several sets of instances show a good performance of the proposed algorithm.     

A multistart adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem

This paper addressed the heterogeneous fixed fleet open vehicle routing problem (HFFOVRP), in which the demands of customers are fulfilled by a fleet of fixed number of vehicles with various capacities and related costs. Moreover, the vehicles start at the depot and terminate at one of the customers. This problem is an important variant of the classical vehicle routing problem and can cover more practical situations in transportation and logistics. We propose a multistart adaptive memory programming metaheuristic with modified tabu search algorithm to solve this new vehicle routing problem. The algorithmic efficiency and effectiveness are experimentally evaluated on a set of generated instances.     

考虑随机旅行时间与二维装载约束的越库配送车辆路径优化

面向越库配送模式下二维装载和车辆路径联合优化,考虑现实配送过程的不确定性因素,提出考虑随机旅行时间和二维装载约束的越库配送车辆路径问题.基于蒙特卡洛模拟与场景分析方法,建立以运输成本、车辆固定成本以及时间窗期望惩罚成本之和最小化为目标的带修正随机规划模型.继而根据问题特征,设计改进的自适应禁忌搜索算法和基于禁忌搜索的多重排序最佳适应装箱算法进行求解.其中,改进的自适应禁忌搜索算法在禁忌搜索算法的基础上引入自适应机制,对不同邻域算子进行动态选择,并提出基于移除-修复策略的多样性机制以增强算法的寻优能力.数值实验表明,所提出的模型与方法能够有效求解考虑随机旅行时间和二维装载约束的越库配送车辆路径问题,自适应与多样性机制能一定程度上增强算法的全局搜索能力.