Heuristics for the bi-objective path dissimilarity problem

In this paper the path dissimilarity problem is considered. The problem has previously been studied within several contexts, the most popular of which is motivated by the need to select transportation routes for hazardous materials. The aim of this paper is to formally introduce the problem as a bi-objective optimization problem, in which a single solution consists of a set of p different paths, and two conflicting objectives arise, on one hand the average length of the paths must be kept low, and on the other hand the dissimilarity among the paths in the set should be kept high. Previous methods are reviewed and adapted to this bi-objective problem, thus we can compare the methods using the standard measures in multi-objective optimization. A new GRASP procedure is proposed and tested against the revised methods, and we show that it is able to create better approximations of efficient frontiers than existing methods.     

Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm

The present study investigates the cost concerns of distribution centers and formulates a vehicle routing problem with time window constraints accordingly. Based on the embedded structure of the original problem, a decomposition technique is employed to decompose the original problems to a clustering problem (main problem) and a set of traveling salesman problems (sub-problems) with time window constraints. This decomposition not only reduces the problem size but also enable the use of simpler solution procedures. A genetic algorithm is developed to solve the clustering problem, while a simple heuristic algorithm is formulated to solve the set of traveling salesman problems. The solution of the original problem is obtained through iterative interactions between the main problem and the set of sub-problems. The performance of the proposed approach is compared with the well-known insertion method and a manual scheduling of a distribution center.     

Vehicle routing problem with a heterogeneous fleet and time windows

In this paper, a problem variant of the vehicle routing problem with time windows is introduced to consider vehicle routing with a heterogeneous fleet, a limited number of vehicles and time windows. A method that extends an existing tabu search procedure to solve the problem is then proposed. To evaluate the performance of the proposed method, experiments are conducted on a large set of test cases, which comprises several benchmark problems from numerous problem variants of the vehicle routing problem with a heterogeneous fleet. It is observed that the proposed method can be used to give reasonably good results for these problem variants. In addition, some ideas are presented to advance the research in heuristics, such as fair reporting standards, publication of benchmark problems and executable routines developed for algorithmic comparison.     

A tabu search approach for the livestock collection problem

We present a problem dealing with transportation of live animals to slaughterhouses. The problem is taken from the Norwegian meat industry, and may be viewed as a vehicle routing problem extended with inventory constraints to ensure a smooth production flow at the slaughterhouse. In addition, several constraints to ensure animal welfare have to be met. These include duration limits for how long animals can stay on the vehicle as well as rules for mixing different animal categories. In this paper, we show that this real-world problem can be solved heuristically, even if it is large both in size and complexity. A tabu search based solution method for the problem is presented, and results from computational testing are given, including comparisons with manual solutions from today's planning system.     

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.     

Iterated local search for the team orienteering problem with time windows

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.     

面向复杂物流配送场景的车辆路径规划多任务辅助进化算法

在现代社会中, 复杂物流配送场景的车辆路径规划问题(Vehicle routing problem, VRP)一般带有时间窗约束且需要提供同时取送货的服务. 这种复杂物流配送场景的车辆路径规划问题是NP-难问题. 当其规模逐渐增大时, 一般的数学规划方法难以求解, 通常使用启发式方法在限定时间内求得较优解. 然而, 传统的启发式方法从原大规模问题直接开始搜索, 无法利用先前相关的优化知识, 导致收敛速度较慢. 因此, 提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm, MBEA), 通过使用迁移优化方法加快算法收敛速度, 其主要思想是通过构造多个简单且相似的子任务用于辅助优化原大规模问题. 首先从原大规模问题中随机选择一部分客户订单用于构建多个不同的相似优化子任务, 然后使用进化多任务(Evolutional multitasking, EMT)方法用于生成原大规模问题和优化子任务的候选解. 由于优化子任务相对简单且与原大规模问题相似, 其搜索得到的路径特征可以通过任务之间的知识迁移辅助优化原大规模问题, 从而加快其求解速度. 最后, 提出的算法在京东物流公司快递取送货数据集上进行验证, 其路径规划效果优于当前最新提出的路径规划算法.     

Integrating public transportation in personalised electronic tourist guides

Personalised electronic tourist guides (PETs) are mobile hand-held devices able to create tourist routes matching tourists' preferences. Transportation information has been identified as one of the most appreciated functionalities of a PET. We model the tourist planning problem, integrating public transportation, as the time-dependent team orienteering problem with time windows (TD-TOPTW) in order to allow PETs to create personalised tourist routes in real-time. We develop and compare two different approaches to solve the TD-TOPTW. Experimental results for the city of San Sebastian show that both approaches are able to obtain routes in real-time.     

求解带时间窗车辆路径问题的改进粒子群算法

通过分析已有粒子群算法对有时间窗约束的车辆路径问题求解质量不高的原因,提出了一种基于粒子交换原理的整数粒子更新方法。采用构造的双层粒子进化算法分别对8个和20个任务点的有时间窗约束的车辆路径问题求解,数值实验结果表明算法的求解精度和耗时均优于已有算法。     

A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problems. It decomposes a target problem into a set of scalar sub-problems and optimizes them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. However, for solving the multi-objective vehicle routing problem with time windows (MO-VRPTW), MOEA/D faces a difficulty that many sub-problems have duplicated best solutions. It is well-known that MO-VRPTW is a challenging problem and has very few Pareto optimal solutions. To address this problem, a novel selection operator is designed in this work to enhance the original MOEA/D for dealing with MO-VRPTW. Moreover, three local search methods are introduced into the enhanced algorithm. Experimental results indicate that the proposed algorithm can obtain highly competitive results on Solomon׳s benchmark problems. Especially for instances with long time windows, the proposed algorithm can obtain more diverse set of non-dominated solutions than the other algorithms. The effectiveness of the proposed selection operator is also demonstrated by further analysis.     

Variable neighborhood search algorithm for heterogeneous traveling repairmen problem with time windows

The focus of this paper is generalized traveling repairman problem (TRP), a special case of the well known and well studied traveling salesman problem (TSP). Because of its specific objective function, that minimizes the sum of overall time all clients wait for until the end of a service, TRP has great applicability potential in client oriented practical problems. Therefore it has been known in literature as traveling deliveryman problem, minimum latency problem and cumulative capacitated vehicle routing problem. However, most studies that have treated TRP related problems have implied that only one repairman is present in the system and/or that all clients are available for service at the beginning of the planning horizon. In this paper we consider a TRP with a heterogeneous fleet of repairmen serving a set of clients whose arrival times are distributed over a planning horizon, i.e. heterogeneous TRPTW (hetTRPTW). For the hetTRPTW we present a mixed integer linear programming model, and a heuristic algorithm based on a variable neighborhood search (VNS) framework. Additionally, we propose a reduction strategy for neighborhoods in the VNS algorithm and test efficiency of implemented algorithms on four benchmark sets of problem instances. Results show that proposed algorithms could be used in real systems for solving small and moderate problem instances.     

物流动态车辆调度问题的混合禁忌搜索算法

在分析动态车辆调度问题的基础上,建立了基于时间轴的动态模型;接着针对该问题在实际中的应用,设计了基于并行节约法和禁忌搜索的混合算法以对动态车辆调度问题进行求解;最后给出算法实现和算例模拟,验证了该算法的有效性。     

时间窗约束下的配送车辆调度问题研究

为解决时间窗约束下的物流配送车辆的多目标调度优化问题,给出了一种基于免疫计算的配送车辆调度优化方案。设计了配送车辆调度问题的数学模型和一种基于非劣邻域支配的多目标调度优化算法,在仿真环境下进行了实验。实验结果表明,算法能够有效地解决物流配送车辆调度问题,具有较好的应用价值。     

基于粒子碰撞的粒子群算法求解带时间窗车辆调度问题*

带时间窗车辆调度问题属于离散NP-hard组合优化问题,传统的粒子群算法在离散域上表现了一定的劣性,对此提出了一种基于粒子碰撞的离散PSO算法来求解该问题。受物体相互碰撞之后物体的速度和位置会发生改变的现象启发,使当前粒子与个体最优和全局最优粒子发生碰撞来更新粒子的位置,以避免传统更新操作中的取整,保证种群的进化能力。采用Solomon’s VRP标准问题集的实例来对算法进行测试,实验结果数据表明了该算法的有效性。     

有时间窗车辆路径问题的捕食搜索算法

有时间窗车辆路径问题是当前物流配送系统研究中的热点问题,该问题具有NP难性质。难以求得最优解或满意解,在建立有时间窗车辆路径问题数学模型的基础上。设计了一种模仿动物捕食策略的捕食搜索算法．该算法利用控制搜索空间的限制大小来实现算法的局域搜索和全局搜索,具有良好的局部集中搜索和跳出局部最优的能力．通过实例计算,并与相关启发式算法比较．取得了满意的结果．     

Truck and trailer routing—Problems,heuristics and computational experience

In the truck and trailer routing problem (TTRP) the vehicle fleet consists of truck units and trailer units with some customers only accessible by truck. For that purpose trailers can be uncoupled en-route at customers where truck sub-tours are built. We discuss several variants of this specific rich vehicle routing problem (RVRP): the TTRP with and without the option of load transfer between truck and trailer as well as the requirement of time windows for delivery. We present computational experience with a simple and flexible hybrid approach which is based on local search and large neighborhood search as well as standard metaheuristic control strategies. This approach which has shown to be rather effective on several other RVRP-classes before can compete with complex state-of-the-art approaches with respect to speed and accuracy on the TTRP too.     

Modeling rolling batch planning as vehicle routing problem with time windows

This paper considers the rolling batch planning problem of grouping and sequencing a given set of slabs into several rolling units in iron and steel industry. The existing mathematical methods often used for the problem are traveling salesman problem (TSP) and vehicle routing problem (VRP), but these methods are not precise, because the position limitation of some slabs in a rolling unit scheduling is not considered. Therefore we suggest a new model, vehicle routing problem with time window (VRPTW) to describe the rolling batch planning problem, in which the position limitation of slabs are quantified as the time constraints. Several solution methods including the genetic algorithm are presented for solving the problem and the computational results show that the genetic algorithm is superior to other methods.In this paper, the vehicle routing problem with time window (VRPTW) of combinational optimization is used to analyze and model the rolling batch planning problem. Genetic algorithm and heuristic are used to solve the problem. Simulation results based on the actual production data show that this model is precise and the genetic algorithm based method is very promising.