The multiple traveling salesman problem: an overview of formulations and solution procedures

The multiple traveling salesman problem (mTSP) is a generalization of the well-known traveling salesman problem (TSP), where more than one salesman is allowed to be used in the solution. Moreover, the characteristics of the mTSP seem more appropriate for real-life applications, and it is also possible to extend the problem to a wide variety of vehicle routing problems (VRPs) by incorporating some additional side constraints. Although there exists a wide body of the literature for the TSP and the VRP, the mTSP has not received the same amount of attention. The purpose of this survey is to review the problem and its practical applications, to highlight some formulations and to describe exact and heuristic solution procedures proposed for this problem.     

考虑充电策略与电池损耗的电动汽车路径优化问题研究

针对目前研究电动物流车辆路径问题的文章未考虑电池损耗对运营成本的影响,且多在充电速率为恒定值的情况下对充电策略进行优化,本文将电动物流车辆在配送货物途中的充电时间和电池损耗成本纳入目标函数并建立了线性规划数学模型,统筹安排车辆行驶路径和充电策略使得物流企业整体运营成本最低。其次,提出了求解该问题的多阶段启发式算法MCWIGALNS。随后,通过多组算例验证了模型和算法的准确性。实验结果表明,考虑充电时间与深度放电成本的模型可以在配送距离不变或略有增加的情况下,较大幅度减少充电时间与电池损耗成本,到达降低运营成本的目的。最后,将算法实验结果与本领域已发表的成果进行比较,证明了MCWIGALNS算法对车辆路径问题具有出色的求解能力,提升了该问题理论成果的实用性。可以为物流企业电动汽车路径策略提供良好借鉴与帮助。     

运力受扰的多车场车辆调度干扰管理问题研究

为解决物流配送系统中因运输车辆毁坏而产生的干扰问题,基于干扰管理思想提出了解决问题的扰动恢复策略与实施方案。在扰动度量的基础上,设计了多车场车辆调度扰动恢复策略,建立相应的干扰管理模型。针对多车场车辆调度干扰管理问题的特有属性,设计了一系列求解简化策略,有效简化了问题的求解空间。结合干扰管理模型的特点,使用改进的遗传算法进行求解。最后给出了一个算例,其结果证明了干扰管理模型与算法的有效性。     

A heuristic algorithm for the period vehicle routing problem

In this paper we consider the period vehicle routing problem, which is the problem of designing routes for delivery vehicles to meet customer service level requirements (not all customers require delivery on every day in the period). A heuristic algorithm, based upon the daily vehicle routing algorithm of Fisher and Jaikumar, is presented and computational results are given for test problems drawn from the literature.     

Two approaches to solving the multi-depot vehicle routing problem with time windows in a time-based logistics environment

This paper presents a two-phase heuristic method that can be used to efficiently solve the intractable multi-depot vehicle routing problem with time windows. The waiting time that was ignored by previous researchers is considered in this study. The necessity of this consideration is verified through an initial experiment. The results indicate that the waiting time has a significant impact on the total distribution time and the number of vehicles used when solving test problems with narrow time windows. In addition, to fairly evaluate the performance of the proposed heuristic method, a meta-heuristic method, which extends the unified tabu search of Cordeau et al., is proposed. The results of a second experiment reveal that the proposed heuristic method can obtain a better solution in the case of narrow time windows and a low capacity ratio, while the proposed meta-heuristic method outperforms the proposed heuristic method, provided that wide time windows and a high capacity ratio are assumed. Finally, a well-known logistics company in Taiwan is used to demonstrate the method, and a comparison is made, which shows that the proposed heuristic method is superior to the current method adopted by the case company.     

Multi-depot vessel routing problem in a direction dependent wavefield

Considerable research has been done on the vehicle routing problem and its variants; however only limited amount of existing work deals with possible environmental conditions and their effects on the vehicle routes. This paper presents the multiple-depot vehicle routing problem for surface vessels, where the vehicles must traverse a time-invariant direction-dependent medium. Our model captures environmental effects and vessel dynamics on the considered paths. Three heuristic solution methods are developed and tested on simulated scenarios. The first approach exactly solves an approximate formulation of the problem, the second approximately solves an approximate problem formulation, while the third approximately solves the exact problem. Performance of the algorithms are compared to assess the tradeoff between computational cost and quality of the found solutions.     

同时集散货物的开放式车辆路径问题研究

本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。 该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。     

Modeling cost-delivery trade-offs for distribution logistics by a generalized PVRP model

This article provides a mathematical model to support management in making decisions about cost-delivery trade-offs in the case of cost-delivery flexibilities in distribution logistics. The optimization problem can be modeled as a bi-objective periodic vehicle routing problem, which is known as NP-hard. In the periodic vehicle routing problem considered in this study, no delivery patterns are pre-defined, instead the patterns are the result of the optimization process of the model. In addition, delivery time flexibilities are incorporated in the model. A heuristic solution method for realistic problem sizes is based on the tabu search procedure, and a real case study illustrates the applicability of the solution concept.     

An investigation into the vehicle routing problem with time windows and link capacity constraints

In this work, we investigate a new, yet practical, variant of the vehicle routing problem called the vehicle routing problem with time windows and link capacity constraints (VRPTWLC). The problem considers new constraints imposed on road links with regard to vehicle passing tonnage, which is motivated by a business project with a Hong Kong transportation company that transports hazardous materials (hazmats) across the city and between Hong Kong and mainland China. In order to solve this computationally challenging problem, we develop a tabu search heuristic with an adaptive penalty mechanism (TSAP) to help manage the company's vehicle fleet. A new data set and its generation scheme are also presented to help validate our solutions. Extensive computational experiments are conducted, showing the effectiveness of the proposed solution approach.     

Vehicle routing using fixed delivery areas

In this paper we consider the problem of vehicle routing using fixed delivery areas. This is the problem of splitting the area serviced by a depot into a number of separate subareas—a single delivery vehicle being assigned to each subarea to supply all the customers within the subarea. A heuristic algorithm is developed for the problem based upon an initial allocation of customers to subareas followed by customer interchanges in an attempt to improve the subareas. Computational results are presented for a number of test problems drawn from the literature.     

Simulated annealing procedure for scheduling competing tasks in flexible manufacturing

This paper presents a simulated annealing SA procedure heuristic for the problem of scheduling N tasks on a machine equipped with an automatic tool changer to minimize the makespan time. The problem is first formulated as a symmetric travelling salesman problem TSP . A local search heuristic procedure is developed, then embedded into SA algorithm to enhance its performance. The implemented SA heuristic has the following features: an exponential acceptance function with non-monotonic cooling schedule, heuristic pre-processing, and a neighbourhood of changing the sequence of a small number of tasks and named the k-interchange procedure. The algorithm is compared with an exact solution method on a set of practical-sized problems. The proposed algorithm performed very well in terms of solution quality and computation time.     

A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling Problem

A new multiperiod variation of the M-traveling salesman problem is introduced. The problem arises in efficient scheduling of optimal interviews among tour brokers and vendors at conventions of the tourism and travel industry. In classical traveling salesman problem vocabulary, a salesman is a tour broker at the convention and a city is a vendor's booth. In this problem, more than one salesman may be required to visit a city, but at most one salesman per time period can visit each city. The heuristic solution method presented is polynomial and is guaranteed to produce a nonconflicting set of salesmen's tours. The results of an implementation of the method for a recent convention are also reported.     

基于改进蚁群算法的低碳车辆路径问题研究

全球气候恶化危及人类生存环境,物流运输过程中产生的大量温室气体则是祸源之一。本文考虑带有碳排放约束的车辆路径问题（VRP）,以车辆行驶里程最短和碳排放量最小为目标,构建了多目标的VRP非线性规划模型。提出了一种改进的蚁群系统算法对该模型进行求解,算法在更新路径上的蚂蚁信息素时引入了混沌扰动机制,此举能降低算法运行时陷入局部最优解的概率并有效提高算法的适应性。同时,对启发因子、状态转移概率、信息素更新等环节进行了优化设计,提高了最优路径的搜索效率。最后,数值仿真实验证明了该算法的求解表现优于同类研究常用的遗传算法和禁忌搜索算法,具有较强的全局寻优能力。在灵敏性和有效性的保证下,本研究所设计的改进蚁群算法能够较好地处理低碳车辆路径问题（LCVRP）。     

Route first—Cluster second methods for vehicle routing

In this paper we consider route first—cluster second methods for the vehicle routing problem. Extensions to the basic method both to improve its effectiveness and to enable it to cope with practical constraints are described. Computational results are given for the method applied to standard vehicle routing problems drawn from the literature.     

多调机环境下的树枝形铁路专用线作业车同步取送优化

围绕服务铁路枢纽地方货物流的小运转作业系统，研究一类多调机环境下的树枝形铁路专用线作业车同步取送优化问题。考虑取送顺序间隔、调机牵引能力等约束条件，以调机作业均衡为上层优化目标，以调机取送成本和货车停留成本最小化为下层优化目标建立双重目标规划模型。根据模型特点，提出融合综合关联度和异步启发式过程的两阶段融合求解方法。该方法首先基于聚类划分思想，引入综合关联度确定调机最佳数量，并对作业区进行划分，从而为调机指派作业范围。进而基于迭代寻优思路，设计异步循环启发式过程，该过程根据多调机取送车作业特点赋予循环体表述，设计循环体更新规则，引入遗传算法中的交叉与变异操作对循环体进行寻优，进而导入人工鱼群聚群行为实现循环体二次寻优，从而完成所有调机在各自作业区内取送顺序的逐步寻优过程。最后，设计实验场景对所提出的两阶段算法进行过程验证，并设计不同规模试验进行对比测试，结果表明了所提算法的有效性和较优性。     

带货物权重的车辆路径问题及遗传算法

考虑一个分销中心、多个零售商组成的分销网络系统中具有柔性车辆能力的带货物权重的车辆路径问题.并根据车辆的满载情况采用了不同的运输策略,即单点运输和多点运输方式.在多点运输方式下,与以往诸多研究不同的是,文章建立了一种基于货物权重的VRP模型——WVRP,即在安排车辆线路时每个零售商的货物需求量也作为一个因素考虑,尽可能使车辆优先供货需求量较大的零售商.最后,针对问题的性质,开发了一种基于划分的遗传算法PB-GA对问题进行求解,并与一般遗传算法及常用的启发式算法进行了分析比较.     

物流配送车辆路径规划模型的知识表示研究

针对物流配送车辆路径规划的实时动态建模问题,以解决模型的目标函数和约束等符号化知识的知识表示及基于知识的求解机制为突破口,提出了以七元组M=(B,O,C,I,P,E,D)表示车辆路径规划模型的知识表示方法--BOCIPED表示法;并以沈阳昌达集团餐饮配送公司为应用背景,设计建立了相应的车辆路径规划问题的建模与求解系统,通过系统的实际应用,验证了系统中BOCIPED表示方法的可行性与有效性.本研究为车辆路径规划这一难题提供由计算机自动生成模型并求解的新方法,有利于建立高智能的物流配送实时调度系统.     

模糊车辆路径问题的一种混合遗传算法

在对模糊车辆路径问题进行简单描述的基础上,通过引入决策者主观偏好值的概念,给出了解决该问题的基本思路,建立了具有模糊特征的车辆路径问题的模糊机会规划模型,提出了求解该问题的一种基于模糊模拟的混合遗传算法。同时,在最小化总行驶距离的目标下,通过随机模拟方法研究了决策者主观偏好值的选择对最终决策目标的影响作用,并给出了其最佳取值范围。     

Approaches to solve the fleet-assignment,aircraft-routing,crew-pairing and crew-rostering problems of a regional carrier

This paper presents the results of a research project funded by a regional carrier operating inter-island services within the Canary Islands (Spain) in addition to services to Morocco and Portugal. It operates between 100 and 150 flights a day using three airline operators. The main scope of the project was to solve fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems on real-world data. The special characteristics of the carrier, flying between 7 am and 11 pm every day, have motivated us to design models and algorithms that are different than the ones addressed in the literature, typically built for large airline companies. This paper shows a solution approach for an integrated fleet-assignment, aircraft-routing and crew-pairing problem covering the flights of a single day. This is a new combinatorial problem that can be considered as a 2-depot vehicle routing problem with driver changes, where the vehicles represent aircrafts and the drivers represent crews. Adapting approaches from the vehicle routing literature, this paper describes a heuristic algorithm based on an integer programming model. In a similar way, this paper also addresses the rostering problem. This problem can be decomposed in smaller problems taking into account operators, bases and crew groups. These problems admit a compact formulation through mixed integer linear programming models which can be tracked by modern general-purpose solvers. This paper illustrates the success of our solution approaches on real-world instances. The airline carrier is currently using these approaches.     

The benefits of planning with normative and heuristic approaches

The effectiveness of planning groups that used normative planning approaches and heuristics were investigated. The quality and innovation in plans developed using each planning approach were compared. Two studies were carried out in three organizations. In the first study, a ‘behavioral’ planning approach and a heuristic were used in a single organization. In the second study, a ‘systems’ planning approach and the heuristic were applied in two organizations. The field experiments demonstrated that the normative planning methods produced plans with superior quality and higher information levels. No differences in plan innovation were observed. Some guides for practice were derived from these findings.