A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics

In this paper, we argue that vehicle routing solutions are often tactical decisions, that should not be changed too often or too much. For marketing or other reasons, vehicle routing solutions should be stable, i.e. a new solution (when e.g. new customers require service) should be as similar as possible to a solution already in use. Simultaneously however, this new solution should still have a good quality in the traditional sense (e.g. small total travel cost). In this paper, we develop a way to measure the difference between two vehicle routing solutions. We use this distance measure to create a metaheuristic approach that will find solutions that are “close” (in the solution space) to a given baseline solution and at the same time have a high quality in the sense that their total distance traveled is small. By using this approach, the dispatcher is offered a choice of Pareto-optimal solutions, allowing him to make a trade-off between changing his existing solution and allowing a longer travel distance. Some experiments are performed to show the effectiveness of the approach.     

Investigation on chaotic motion in hysteretic non-linear suspension system with multi-frequency excitations

This paper presents the investigation on possible chaotic motion in a vehicle suspension system with hysteretic non-linearity, which is subjected to the multi-frequency excitation from road surface. The Melnikov’s function is used to derive the critical condition for the chaotic motion, and then it is investigated that the effects of parameters in non-linear damping on the chaotic field. The path from quasi-periodic to chaotic motion is found via Poincaré map and Lyapunov exponents.     

Vehicle and personnel routing optimization in the service sector: application to water distribution and treatment

We present an overview of the author’s Ph.D. thesis, supervised by P. Dejax and N. Bostel, which was defended in February 2006 at école des Mines de Nantes, France. The thesis is written in French, and is available at . It was conducted in the context of a research contract with a water distribution company. In a first section, we define multiperiod routing problems for service technicians. In a second section, we present some heuristics and a memetic algorithm used to solve these problems. The third section introduces optimal and near-optimal approaches based on column generation. Finally, we present some applications to the real-life case. The methods presented in Sects. 2, 3 and 4 were tested over several sets of problems, based on real-life statistics provided by the company.      

Capillary electrophoresis determinative and GC-MS confirmatory method for water-soluble organic acids in airborne particulate matter and vehicle emission

Urban fine airborne particulate matter (PM2.5) and vehicle emission samples were studied for water-soluble low-molecular-weight carboxylic acids using CE with indirect UV detection. Further identification of these acids was achieved using GC-MS as their butyl esters (after derivatization with BF3/butanol). Several dicarboxylic acids in the range C2-C10 including straight-chain, branched-chain, cis- and trans-unsaturated, and aromatic acids were confirmed by GC-MS. In addition, aromatic acids such as benzoate, phthalate, terephthalate, isophthalate, and 4-methylphtalate were present in such samples, but some of these were not well resolved by the used CE method. Oxocarboxylic acids (Cn(w) with n > 4) were also identified by GC-MS but not determined by CE due to lack of standards. The rapidity and simplicity of the CE method were clearly demonstrated, and the method was observed to be advantageous for routine monitoring of water-soluble organic acids in airborne PM2.5 and vehicle emission at low microg/L levels.     

The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method

This paper focuses on vehicle routing problems with profits and addresses the so-called Capacitated Team Orienteering Problem. Given a set of customers with a priori known profits and demands, the objective is to find the subset of customers, for which the collected profit is maximized, and to determine the visiting sequence and assignment to vehicle routes assuming capacity and route duration restrictions. The proposed method adopts a hierarchical bi-level search framework that takes advantage of different search landscapes. At the upper level, the solution space is explored on the basis of the collected profit, using a Filter-and-Fan method and a combination of profit oriented neighborhoods, while at the lower level the routing of customers is optimized in terms of traveling distance via a Variable Neighborhood Descent method. Computational experiments on benchmark data sets illustrate the efficiency and effectiveness of the proposed approach. Compared to existing results, new upper bounds are produced with competitive computational times.     

基于实际路网情境的配送车辆调度优化

在实际路网情境下结合车道数、车道宽度、路口信号灯设置等路网物理特性,构建了考虑综合交通阻抗的多车型车辆调度模型,提出了两阶段求解策略:第1阶段设计了改进A-star精确解算法用于计算客户时间距离矩阵;第2阶段针对实际路网的特征设计了混合模拟退火算法求解调度方案。以大连市某配送中心运营实例进行路网情境仿真试验,结果表明:改进A-star算法较改进Dijkstra算法具有更短的路径搜索时间;混合模拟退火算法求解结果较实际调度方案优化了13.1% 的综合成本;路网增流、区域拥堵和路段禁行三类路网情境均能对配送方案的车辆配置、路径选择、客户服务次序、作业时间和违约费用等5方面内容产生干扰,调度计划的制定需要详细考虑这些因素的变化。     

A review of mobility metrics for next generation vehicle mobility models

In the United States, the NATO Reference Mobility Model (NRMM) has been used for evaluating military ground vehicle mobility and the Vehicle Cone Index (VCI) has been selected as a mobility metric. VCI represents the minimum soil strength required for a vehicle to consistently make a specific number of passes, usually one or fifty passes. In the United Kingdom, the Mean Maximum Pressure (MMP) has been adopted as a metric for assessing military vehicle cross-country mobility. MMP is the mean value of the maxima occurring under all the wheel stations of a vehicle. Both VCI and MMP are empirically based. This paper presents a review of the basis upon which VCI and MMP were developed, as well as their applications to evaluating vehicle mobility in practice. With the progress in terramechanics and in modelling and simulation techniques in recent years, there is a growing desire to develop physics-based mobility metrics for next generation vehicle mobility models. Based on the review, criteria for selecting physics-based mobility metrics are proposed. Following these criteria, metrics for characterizing military vehicle traction limits and traversability on a given operating area are recommended.     

Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care

This paper addresses a vehicle scheduling problem encountered in home health care logistics. It concerns the delivery of drugs and medical devices from the home care company’s pharmacy to patients’ homes, delivery of special drugs from a hospital to patients, pickup of bio samples and unused drugs and medical devices from patients. The problem can be considered as a special vehicle routing problem with simultaneous delivery and pickup and time windows, with four types of demands: delivery from depot to patient, delivery from a hospital to patient, pickup from a patient to depot and pickup from a patient to a medical lab. Each patient is visited by one vehicle and each vehicle visits each node at most once. Patients are associated with time windows and vehicles with capacity. Two mixed-integer programming models are proposed. We then propose a Genetic Algorithm (GA) and a Tabu Search (TS) method. The GA is based on a permutation chromosome, a split procedure and local search. The TS is based on route assignment attributes of patients, an augmented cost function, route re-optimization, and attribute-based aspiration levels. These approaches are tested on test instances derived from existing VRPTW benchmarks.