Effective Heuristic Procedures for a Field Technician Scheduling Problem

This paper addresses a field technician scheduling problem faced by many service providers in telecommunication industry. The problem is to assign a set of jobs, at different locations with time windows, to a group of field technicians with different job skills. Such a problem can be viewed as a generalization of the well-known vehicle routing problem with time windows since technician skills need to be matched with job types. We designed and tested several heuristic procedures for solving the problem, namely a greedy heuristic, a local search algorithm, and a greedy randomized adaptive search procedure (GRASP). Our computational results indicate that GRASP is the most effective among them but requires more CPU time. However, the unique structure of GRASP allows us to exploit parallelism to achieve linear speed-up with respect to the number of machines used.     

Solving routing problems with pairwise synchronization constraints

Pairwise route synchronization constraints are commonly encountered in the field of service technician routing and scheduling and in the area of mobile care. Pairwise route synchronization refers to constraints that require that two technicians or home care workers visit the same location at exactly the same time. We consider constraints of this type in the context of the well-known vehicle routing problem with time windows and a generic service technician routing and scheduling problem. Different approaches for dealing with the problem of pairwise route synchronization are compared and several ways of integrating a synchronization component into a metaheuristic algorithm tailored to the original problems are analyzed. When applied to benchmark instances from the literature, our algorithm matches almost all available optimal values and it produces several new best results for the remaining instances.

     

A rich vehicle routing problem dealing with perishable food: a case study

This paper presents a successful application of operations research techniques in guiding the decision making process to achieve a superior operational efficiency in core activities. We focus on a rich vehicle routing problem faced by a Portuguese food distribution company on a daily basis. This problem can be described as a heterogeneous fleet site dependent vehicle routing problem with multiple time windows. We use the adaptative large neighbourhood search framework, which has proven to be effective to solve a variety of different vehicle routing problems. Our plans are compared against those of the company and the impact that the proposed decision support tool may have in terms of cost savings is shown. The algorithm converges quickly giving the planner considerably more time to focus on value-added tasks, rather than manually correct the routing schedule. Moreover, contrarily to the necessary adaptation time of the planner, the tool is quite flexible in following market changes, such as the introduction of new customers or new products.     

Heuristic solution approaches for the cumulative capacitated vehicle routing problem

Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.     

A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions

In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented.     

Managing pharmaceuticals delivery service using a hybrid particle swarm intelligence approach

Medicines or drugs have unique characteristics of short life cycle, small size, light weight, restrictive distribution time and the need of temperature and humidity control (selected items only). Thus, logistics companies often use different types of vehicles with different carrying capacities, and considering fixed and variable costs in service delivery, which make the vehicle assignment and route optimization more complicated. In this study, we formulate the problem to a multi-type vehicle assignment and mixed integer programming route optimization model with fixed fleet size under the constraints of distribution time and carrying capacity. Given non-deterministic polynomial hard and optimal algorithm can only be used to solve small-size problem, a hybrid particle swarm intelligence (PSI) heuristic approach, which adopts the crossover and mutation operators from genetic algorithm and 2-opt local search strategy, is proposed to solve the problem. We also adapt a principle based on cost network and Dijkstra’s algorithm for vehicle scheduling to balance the distribution time limit and the high loading rate. We verify the relative performance of the proposed method against several known optimal or heuristic solutions using a standard data set for heterogeneous fleet vehicle routing problem. Additionally, we compare the relative performance of our proposed Hybrid PSI algorithm with two intelligent-based algorithms, Hybrid Population Heuristic algorithm and Improved Genetic Algorithm, using a real-world data set to illustrate the practical and validity of the model and algorithm.

     

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

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

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory, and the further experimental results on instances collected from real colour-coating production also show that the proposed ILS algorithm is more effective and efficient than the currently adopted manual scheduling method.     

面向电商终端物流配送的电动车配置与路径集成优化

在电子商务终端物流配送方面,存在能力与需求的矛盾。一方面,电动车存在货物容量约束和电池电量约束,配送能力有限;另一方面,一个物流配送点需要为众多的消费者进行门到门的配送,配送任务繁重。针对电子商务环境下终端物流配送规模大、电动车货物容量和行驶里程有限的问题,建立电商终端物流配送的电动车配置与路径规划集成优化模型,并提出一种基于临近城市列表的双策略蚁群算法,实现物流配送电动车辆配置与配送路径集成优化。该模型以电动车辆数最少和总路径最短为目标,以电动车货物容量和电池续航里程为约束,是带容量的车辆路径问题的进一步扩展,属于双容量约束路径规划问题。双策略蚁群算法在货物容量和续航里程的约束下,将蚁群搜索策略分为两类,即基于临近城市列表的局部搜索策略和全局搜索策略,在提高搜索效率的同时防止陷入局部优化。最后,通过阿里巴巴旗下菜鸟网络科技有限公司在上海的30组真实配送数据进行了测试,验证双策略蚁群算法显著优于一般蚁群算法。     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

战时备件配送的MDVRPTW问题研究

战时备件配送的车辆调度是提高装备保障效率的关键因素.以装备效能损失最小化为车辆调度的目标,建立了问题的M DVRPTW模型,并应用蚁群算法对问题进行了求解.算法中,根据问题特征改进了状态转移规则,设计了串行和并行两种路线构造方法,并应用局部搜索模块对蚂蚁构造的路线进行改进.对算例的计算实验表明,串行路线构造方法在精度和速度两方面均优于并行路线构造方法.     

Designing routes for WEEE collection: the vehicle routing problem with split loads and date windows

This paper presents an integer programming model and describes a GRASP based algorithm to solve a vehicle routing and scheduling problem for the collection of Waste of Electric and Electronic Equipment (WEEE). The difficulty of this problem arises from the fact that it is characterized by four variants of the vehicle routing problem that have been studied independently in the literature, but not together. The experimental analysis on a large set of randomly-generated instances shows the good performance of the proposed algorithm. Moreover, computational results using real data show that the method outperforms real existing approaches to reverse logistics.     

基于交通流的多模糊时间窗车辆路径优化

研究了基于交通流的多模糊时间窗车辆路径问题,考虑了实际中不断变化的交通流以及客户具有多个模糊时间窗的情况,以最小化配送总成本和最大化客户满意度为目标,构建基于交通流的多模糊时间窗车辆路径模型。根据伊藤算法的基本原理,设计了求解该模型的改进伊藤算法,结合仿真算例进行了模拟计算,并与蚁群算法的计算结果进行了对比分析,结果表明,利用改进伊藤算法求解基于交通流的多模糊时间窗车辆路径问题,迭代次数小,效率更高,能够在较短的时间内收敛到全局最优解,可以有效的求解多模糊时间窗车辆路径问题。     

A tabu search algorithm for the multi-trip vehicle routing and scheduling problem

This paper describes a novel tabu search heuristic for the multi-trip vehicle routing and scheduling problem (MTVRSP). The method was developed to tackle real distribution problems, taking into account most of the constraints that appear in practice. In the MTVRSP, besides the constraints that are common to the basic vehicle routing problem, the following ones are present: during each day a vehicle can make more than one trip; the customers impose delivery time windows; the vehicles have different capacities considered in terms of both volume and weight; the access to some customers is restricted to some vehicles; the drivers' schedules must respect the maximum legal driving time per day and the legal time breaks; the unloading times are considered.     

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.     

城市配送车辆路径优化集束式算法的客户点归并策略

VRP问题的研究起步较早,求解方法也非常丰富,然而,面对客户规模庞大,交通网络复杂的多约束车辆优化调度问题,现有算法显得无能为力.为有效解决需求点规模庞大的城市配送车辆优化调度问题,提出一种新的两阶段启发式算法——集束式算法,采用"集中后分派,分派后扩展"的思想,对末梢客户和同路段客户进行客户点合并,从全局上降低搜索范围,并提出相关客户点归并算法.     

A new hybrid genetic algorithm for the capacitated vehicle routing problem

Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.     

Routing and scheduling in a flexible job shop by tabu search

A hierarchical algorithm for the flexible job shop scheduling problem is described, based on the tabu search metaheuristic. Hierarchical strategies have been proposed in the literature for complex scheduling problems, and the tabu search metaheuristic, being able to cope with different memory levels, provides a natural background for the development of a hierarchical algorithm. For the case considered, a two level approach has been devised, based on the decomposition in a routing and a job shop scheduling subproblem, which is obtained by assigning each operation of each job to one among the equivalent machines. Both problems are tackled by tabu search. Coordination issues between the two hierarchical levels are considered. Unlike other hierarchical schemes, which are based on a one-way information flow, the one proposed here is based on a two-way information flow. This characteristic, together with the flexibility of local search strategies like tabu search, allows to adapt the same basic algorithm to different objective functions. Preliminary computational experience is reported.     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

A hybrid generational genetic algorithm for the periodic vehicle routing problem with time windows

We propose a new population-based hybrid meta-heuristic for the periodic vehicle routing problem with time windows. This meta-heuristic is a generational genetic algorithm that uses two neighborhood-based meta-heuristics to optimize offspring. Local search methods have previously been proposed to enhance the fitness of offspring generated by crossover operators. In the proposed method, neighborhood-based meta-heuristics are used for their capacity to escape local optima, and deliver optimized and diversified solutions to the population of the next generation. Furthermore, the search performed by the neighborhood-based meta-heuristics repairs most of the constraint violations that naturally occur after the application of the crossover operators. The genetic algorithm we propose introduces two new crossover operators addressing the periodic vehicle routing problem with time windows. The two crossover operators are seeking the diversification of the exploration in the solution space from solution recombination, while simultaneously aiming not to destroy information about routes in the population as computing routes is NP-hard. Extensive numerical experiments and comparisons with all methods proposed in the literature show that the proposed methodology is highly competitive, providing new best solutions for a number of large instances.