变邻域模拟退火算法求解速度时变的VRPTW问题

本文在经典的带时间窗的车辆路径问题(VRPTW)的基础上,考虑不同时间段车辆行驶速度不同的情况,研究速度时变的带时间窗车辆路径问题(TDVRPTW),使问题更具实际意义。本文用分段函数表示不同时间段下的车辆行驶速度,并解决了速度时变条件下行驶时间计算的问题。针对模拟退火算法(SA)在求解VRPTW问题时易陷入局部最优解,变邻域搜索算法(VNS)在求解VRPTW问题时收敛速度慢的问题,本文将模拟退火算法以一定概率接受非最优解的思想和变邻域搜索算法系统地改变当前解的邻域结构以拓展搜索范围的思想结合起来,提出了一种改进的算法——变邻域模拟退火算法(SAVN),使算法在退火过程中一陷入局部最优解就改变邻域结构,更换搜索范围,以此提升算法跳出局部最优解的能力,加快收敛速度。通过在仿真实验中将SAVN算法的求解结果与VNS算法、SA算法进行对比,验证了SAVN算法确实能显著提升算法跳出局部最优解的能力。     

混合启发式算法求解多配送人员车辆路径问题

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。     

时变条件下带时间窗车辆调度问题的模拟退火算法

带时间窗车辆调度问题(VRPTW)是一类要求满足容积和时间窗约束的车辆路径优化问题,现 有大部分相关文献只考虑了车辆行驶速度恒定的情况,忽略了各种动态因素的影响.本文研究的时变条件下带时间窗车辆调度问题将车辆行驶速度考虑成时变分段函数,并利用模拟退火算法进行求解,最后通过实验结果说明算法的有效性.     

求解带时间窗车辆路径问题的改进离散花朵授粉算法

针对当前算法在求解带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)时存在精度、效率方面的不足,提出一种改进的离散花朵授粉算法.算法在基本花朵授粉算法的基础上进行离散化,使其适合求解带时间窗车辆路径问题,重新定义花朵授粉算子操作.为了提高求解精度和效率,设计了随机插入、路径内的2-opt、交换和逆序操作,为了增加种群间信息的交互,结合改进的遗传算子.通过11个测试算例表明,改进的离散花朵授粉算法在求解VRPTW是行之有效的,与文献中其他算法比较,算法在精度、效率和鲁棒性方面具有优势.     

遗传算法与蚂蚁算法的融合在带时间窗的车辆路径问题中的应用

对带时间窗的车辆路径问题(VRPTW)的求解分为两个过程,先由遗传算法求解出初步的可行解,由此生成信息素初始分布,而后采用蚂蚁算法找出问题的最优解或近似最优解.通过具体算例,从数值计算上探索了遗传算法和蚂蚁算法融合后的优化能力,获得了满意的效果.     

一种带时间窗和车辆数目限制的车辆路线问题及其算法

本文提出了带时间窗和车辆数目限制的车辆路线问题的数学模型,针对该问题的特征构造了一种路线生成算法和禁忌搜索算法,并对Solomon提出的C1、R1、RC1类数据集给出了数值运算的结果,实验结果表明算法是有效的.     

一种改进的禁忌搜索算法及其在连续全局优化中的应用

禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。     

多行程车辆路径问题和配送中心定位问题的研究

为了同时解决多行程车辆路径问题和配送中心的定位问题,首先开发了一个以最小化总成本为目标的数学模型,其中总成本包括运输成本和车辆启动成本.然后设计了一个启发式算法解决这个问题,包括三个阶段:第一阶段是找到初始定位并进行路线安排,第二阶段采用模拟退火(SA)的逻辑和交换算法来获得更好的路线,最后阶段是改善由模拟退火算法中当前温度控制的位置.通过标准样例进行的实验结果表明,该算法可以更好地获得一个配送中心定位和有效的相关路线安排.最后,数值实验指出:1)选择不同类型行程的配送方式取决于每辆车的启动成本和单位距离的运输成本;2)使用大容量车辆可以更好地减少运输距离.3)增加服务时间可以有效地减少所需车辆的数量,这三个结果对于多行程车辆路径问题和配送中心的定位问题的管理决策都具有一定的实用价值.     

基于混合非单调下降条件的直接搜索方法

基于混合非单调下降条件提出了一种网格步长的更新策略.这种策略要求发现强最小网格单元框时网格步长快速下降,而发现其他拟最小网格单元框时缓慢下降.这种混合非单调下降策略可以避免网格步长下降太快,又能够比单纯非单调下降条件更好地保证直接搜索算法的收敛性.基于这一策略,本文提出一个直接搜索算法,并证明了该算法的全局收敛性.数值试验表明,本文提出的算法是很有竞争力的直接搜索算法.     

多行程车辆路径问题中变邻域搜索算法的应用

多行程车辆路径问题是标准车辆路径问题的一个变体,每个车辆在运行期间可以使用不止一次.对于这种NP-HARD问题,提出了一个改进变邻域搜索算法并设计了四个邻域结构用于求解和制定多行程路径问题的调度规划.算法测试了一组标准实例问题,获得的解决方法与文献中提出的三种不同数据集进行比较计算证明,算法提供了较高质量的求解结果.最后采用三个标准函数进行数值计算,与PSO和GA算法进行比较证明,提出的VNS算法虽然运行花费时间较长,但是达到全局收敛性的比率和全局收敛性都远超其他两种算法.     

Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation

This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.     

A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.     

Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows

This work deals with a new combinatorial optimization problem, the two-dimensional loading capacitated vehicle routing problem with time windows which is a realistic extension of the well known vehicle routing problem. The studied problem consists in determining vehicle trips to deliver rectangular objects to a set of customers with known time windows, using a homogeneous fleet of vehicles, while ensuring a feasible loading of each vehicle used. Since it includes NP-hard routing and packing sub-problems, six heuristics are firstly designed to quickly compute good solutions for realistic instances. They are obtained by combining algorithms for the vehicle routing problem with time windows with heuristics for packing rectangles. Then, a Memetic algorithm is developed to improve the heuristic solutions. The quality and the efficiency of the proposed heuristics and metaheuristic are evaluated by adding time windows to a set of 144 instances with 15–255 customers and 15–786 items, designed by Iori et al. (Transport Sci 41:253–264, 2007) for the case without time windows.     

Heuristics to Schedule Service Engineers within Time Windows

This paper describes the development of a set of heuristics for tackling vehicle routeing problems with time windows (VRPTW) subject to uncertain demand where schedules are prepared interactively. Many public utility companies, e.g. gas, water, electricity, are now having to quote very specific times for visits to customers, both for regular service and emergency call-outs. The heuristics developed produce good tours by sequencing visits on the basis of closeness to existing visits. Tours are developed as and when demand occurs so that the customer is given an immediate appointment time, rather than waiting for a number of requests for service to be received. Simple methods to construct time windows will also be discussed.     

A multi-shift vehicle routing problem with windows and cycle times

In many applications of the vehicle routing problem with time windows (VRPTW), goods must be picked up within desired time frames. In addition, they have some limitations on their arrival time to the central depot. In this paper, we present a new version of VRPTW that minimizes the total cycle time of the goods. In order to meet the time windows and also minimize the cycle time, the courier’s schedule is allowed to vary. An algorithm, named VeRSA, is proposed to solve this problem. VeRSA employs concepts of scheduling theorems and algorithms to determine feasible routes and schedules of the available couriers. We prove a theoretical lower bound that provides a useful bound on the optimality gap. We also conduct a set of numerical experiments. VeRSA obtains a feasible solution faster than solving the MIP. The optimality gap using our proposed lower bound is smaller than the gap found with the standard LP relaxation.     

Optimizing departure times in vehicle routes

Most solution methods for the vehicle routing problem with time windows (VRPTW) develop routes from the earliest feasible departure time. In practice, however, temporary traffic congestion make such solutions non-optimal with respect to minimizing the total duty time. Furthermore, the VRPTW does not account for driving hours regulations, which restrict the available travel time for truck drivers. To deal with these problems, we consider the vehicle departure time optimization (VDO) problem as a post-processing of a VRPTW. We propose an ILP formulation that minimizes the total duty time. The results of a case study indicate that duty time reductions of 15% can be achieved. Furthermore, computational experiments on VRPTW benchmarks indicate that ignoring traffic congestion or driving hours regulations leads to practically infeasible solutions. Therefore, new vehicle routing methods should be developed that account for these common restrictions. We propose an integrated approach based on classical insertion heuristics.     

The vehicle routing problem with coupled time windows

In this article we introduce the vehicle routing problem with coupled time windows (VRPCTW), which is an extension of the vehicle routing problem with time windows (VRPTW), where additional coupling constraints on the time windows are imposed. VRPCTW is applied to model a real-world planning problem concerning the integrated optimization of school starting times and public bus services. A mixed-integer programming formulation for the VRPCTW within this context is given. It is solved using a new meta-heuristic that combines classical construction aspects with mixed-integer preprocessing techniques, and improving hit-and-run, a randomized search strategy from global optimization. Solutions for several randomly generated and real-world instances are presented.     

A school bus scheduling problem

This paper introduces a school bus scheduling problem wherein trips for each school are given. A trip consists of a sequence of bus stops and their designated school. Each school has its fixed time window within which trips should be completed. A school bus can serve multiple trips for multiple schools. The school bus scheduling problem seeks to optimize bus schedules to serve all the given trips considering the school time windows. We first model the problem as a vehicle routing problem with time windows (VRPTW) by treating a trip as a virtual stop. Two assignment problem based exact approaches are then proposed for special cases and a heuristic algorithm is proposed for more general cases. Benchmark problems and computational experiments are presented. Computational experiments show the effectiveness of the proposed approaches.     

A route-neighborhood-based metaheuristic for vehicle routing problem with time windows

In this paper, a two-stage metaheuristic based on a new neighborhood structure is proposed to solve the vehicle routing problem with time windows (VRPTW). Our neighborhood construction focuses on the relationship between route(s) and node(s). Unlike the conventional methods for parallel route construction, we construct routes in a nested parallel manner to obtain higher solution quality. Valuable information extracted from the previous parallel construction runs is used to enhance the performance of parallel construction. In addition, when there are only a few unrouted customers left, we design a special procedure for handling them. Computational results for 60 benchmark problems are reported. The results indicate that our approach is highly competitive with all existing heuristics, and in particular very promising for solving problems of large size.     

A synthesis of assignment and heuristic solutions for vehicle routing with time windows

This paper proposes a three-stage method for the vehicle-routing problem with time window constraints (VRPTW). Using the Hungarian method the optimal customer matching for an assignment approximation of the VRPTW, which is a travel time-based relaxation that partially respects the time windows, is obtained. The assignment matching is transformed into feasible routes of the VRPTW via a simple decoupling heuristic. The best of these routes, in terms of travelling and vehicle waiting times, form part of the final solution, which is completed by the routes provided by heuristic methods applied to the remainder of the customers. The proposed approach is tested on a set of standard literature problems, and improves the results of the heuristic methods with respect to total travel time. Furthermore, it provides useful insights into the effect of employing optimal travel time solutions resulting from the assignment relaxation to derive partial route sets of the VRPTW.