有软时窗多车场开放式车辆路径及其禁忌搜索

有软时窗约束多车场开放式车辆路径问题是在基本的车辆路径问题上增加了时间窗约束和多车场作业的一种变化形式,是一个典型的NP-难问题。建立了问题模型,运用改进的禁忌搜索算法测试了算例。快速获得的高质量解验证了模型的正确性和算法性能的优良性。     

多配送中心下生鲜农产品同步取送选址-路径优化

多配送中心下生鲜农产品配送工作中配送中心选址和车辆取送是两项最为重要的工作，故本文研究带同步取送的生鲜农产品选址?路径问题。首先，建立考虑车辆容量、货物作业时间、取送作业时间窗等约束条件的非线性规划模型，模型以各配送区域内产生的运输成本、惩罚费用、货损费用总和最小为目标函数。然后，根据模型特点设计融合中心评估指数和改进遗传算法的启发式算法，算法先利用中心评估指数确定配送中心和车辆的配送区域，将区域划分的信息传递给改进遗传算法进行各区域内的路径优化。最后，通过对比取送分离和同步取送两种配送方式验证本文提出的配送模式及模型是合理有效的，可为企业的生鲜农产品配送提供决策依据。     

大型铁路客运站车底取送作业模型研究

客运站旅客列车车底取送作业关系着始发、终到列车占用到发线、客技线的起止时间,能否快速、合理地制定旅客列车车底取送作业计划,直接影响着铁路客运站作业效率。通过考虑客技线的运用、咽喉区的交叉干扰等因素对旅客列车车底取送作业计划的影响,考虑在保证晚点始发旅客列车数目最少的同时将晚点始发列车的晚点时间控制在可接受的范围内,使得晚点始发的列车也可正常出发。提出列车晚点时间应控制在合理范围内的方法,在推算出车底出、入库时间窗的基础上,利用入库时间窗和出库时间窗作为约束条件确定车底出入库时刻,加入相关参数来放松硬约束以达到合理安排车底取送计划的目的。以整备后旅客列车的晚点始发的列车总数目最少为目标的方法,建立车底取送作业模型,运用模拟退火算法对该模型进行求解。实例表明,提出的模型及算法能够快速、合理地制定旅客列车车底取送作业计划。     

蚂蚁算法在带时间窗车辆路径问题中的应用及参数分析

带时间窗的车辆路径问题是一个典型的NP-Hard问题,本文将蚂蚁算法应用于带时间窗车辆路径问题,构造了该问题的表达方法,建立了相应的算法模型,对算法参数进行了分析并提出了相应的参数改进方案。仿真实验表明,改进后的算法可以快速、有效地求解带时间窗车辆路径问题,具有较好的可行性和适用性。     

汽车零部件Milk-run车辆调度优化模型和算法

为了寻求汽车零部件采用循环取货时车辆的最优路径,提出将每个供应商零部件循环、分批提取使车辆尽可能满载的建模思路,建立具有车辆容积、车辆到达时间窗、供应商供货动态时间窗、车辆最大行程约束的车辆调度优化模型,设计了用于求解该模型的改进启发式节约算法。最后通过算例验证了多重约束模型及算法的有效性。     

带时间窗和服务顺序约束的多需求车辆路径问题

研究顾客具有多种需求,分别需要由不同类型车辆提供服务,且同一顾客多种需求的服务时间具有固定先后顺序的车辆路径问题.在考虑各个顾客需求的服务时间窗,同一顾客不同需求的服务顺序、服务时间间隔,以及各种车型的车容量及最大行驶时间等约束的前提下,以满足顾客多种需求的车辆运行成本和等待成本之和极小化为目标,建立混合整数规划模型.进一步设计求解模型的联合优化遗传算法,并利用车辆路径问题的标准测试集构造具有两种需求的测试算例,分别利用所提出的联合优化遗传算法与文献中的两阶段遗传算法进行模拟计算与分析,验证所提出算法的有效性.将经典的单一需求车辆路径问题推广到多种需求的情形,建立带约束的多需求车辆路径问题的数学模型并设计求解模型的有效算法,为解决实际问题提供了决策依据.     

时间窗约束下农产品物流配送路径优化研究

农产品需求量增加对物流配送提出较高挑战,基于此提出时间窗约束下农产品物流配送路径优化方法研究。依客户预期服务时间需求,取混合时间窗约束函数确定时间窗、物流配送车辆最大载重、配送路径长度与物流配送车辆约束条件,构建农产品物流配送路径优化模型;基于农产品物流配送需求改进传统遗传算法,求解构建模型,即获农产品物流配送路径优化结果。实验结果显示：相较生鲜农产品多车型冷链物流车辆路径优化,所提方法最优农产品物流配送路径获取迭代次数更少、配送路径长度更短、总成本更低,应用性能更佳。     

基于启发式带时间窗的车辆路径规划问题求解

车辆路径规划问题广泛地存在于现代物流行业中, 该问题属于NP难的组合优化问题. 随着客户需求的多样化、道路限行等因素的影响, 该问题变得更加的复杂, 采用传统的组合优化方法和运筹学方法往往难以求解. 本文对一类常见的带时间窗的车辆路径规划问题进行了研究, 根据时间窗参数来调整客户的优先级, 以减少车辆的等待时间, 由此改进了几个常见的启发式算法, 并对56个常见的车辆路径规划问题进行了测试, 实验结果表明, 改进的节约算法在带容量约束的车辆路径问题中效果较好, 改进的插入法则在带时间窗的车辆路径问题中具有优越性, 另外, 改进的启发式算法在4个测试用例上使用更多车辆时可使总路程优于已知最优值.     

求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法

带时间窗和容量约束的车辆路径问题是车辆路径问题重要的扩展之一,属于NP难题,精确算法的求解效率较低,且对于较大规模问题难以在有限时间内给出最优解.为了满足企业和客户快速有效的配送需求,使用智能优化算法可以在有限的时间内给出相对较优解.研究了求解带容量和时间窗约束车辆路径问题的改进离散蝙蝠算法,为增加扰动机制,提高搜索速度和精度,在对客户点按其所在位置进行聚类的基础上,在算法中引入了变步长搜索策略和两元素优化方法进行局部搜索.仿真实验结果表明,所设计算法具有较高寻优能力和较强的实用价值.     

网约拼车出行的乘客车辆匹配及路径优化

城市道路拥堵严重及共享理念的盛行带来了拼车出行的兴起。出行线路相似的乘客共乘一辆车,可提高座位利用率、节省费用、缓解交通压力。以带时间窗约束的无换乘多车辆静态拼车问题为研究背景,从车辆使用费、途中走行成本及到达时间窗惩罚成本3个方面建立乘客车辆匹配及路径优化的目标函数,以车辆容量、乘客出发及到达时间窗、路径无迂回、乘客车辆匹配无重叠等限制构建模型约束条件,采用演化策略算法求解问题,根据模型特征设计编码解码规则,解码结果可同时获得车辆乘客匹配关系和走行路径,采用交叉变异操作更新迭代个体种群,进而求得最优解。运用MATLAB求解算例验证了模型可行性及算法有效性,结果表明算法能快速响应静态拼车问题,在较短时间即可给出乘客车辆的先后匹配关系及车辆走行路径,拼车方案相比独自出行能节省更多成本。     

基于遗传算法的集送一体化的车辆路径问题

有时间窗的集送货一体化的车辆路径问题(VRPPDTW)是对经典的车辆路径问题(VRP)的扩展,是一类重要的组合优化问题,但是目前对该问题的研究非常有限。论文采用了新的染色体编码方法,设计了遗传算法对该问题进行求解。在求解过程中,对集送一体化、多种配送车辆类型的问题进行了有效处理,同时考虑了车辆载重量和时间窗等约束。最后的实验结果表明,该算法可以求得这类车辆路径问题的最优解或次优解。     

Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO

Two solution representations for solving the generalized multi-depot vehicle routing problem with multiple pickup and delivery requests (GVRP-MDMPDR) is presented in this paper. The representations are used in conjunction with GLNPSO, a variant of PSO with multiple social learning terms. The computational experiments are carried out using benchmark test instances for pickup and delivery problem with time windows (PDPTW) and the generalized vehicle routing problem for multi-depot with multiple pickup and delivery requests (GVRP-MDMPDR). The preliminary results illustrate that the proposed method is capable of providing good solutions for most of the test problems.     

Integrating territory design and routing problems

An integrated model combining territorial design and vehicle routing is presented. For the routing problem, the simultaneous pickup and delivery is considered subject to time windows, while districting is aimed at minimizing the length of the longest zone of the route. A corresponding mixed integer programming model is considered and the results of the numerical experiment are provided.     

A branch-and-price-and-check model for the vehicle routing problem with location congestion

This paper considers a vehicle routing problem with pickup and delivery, time windows and location congestion. Locations provide a number of cumulative resources that are utilized by vehicles either during service (e.g., forklifts) or for the entirety of their visit (e.g., parking bays). Locations can become congested if insufficient resources are available, upon which vehicles must wait until a resource becomes available before proceeding. The problem is challenging from a computational standpoint since it incorporates the vehicle routing problem and the resource-constrained project scheduling problem. The main contribution of this paper is a branch-and-price-and-check model that uses a branch-and-price algorithm that solves the underlying vehicle routing problem, and a constraint programming subproblem that checks the feasibility of the location resource constraints, and then adds combinatorial nogood cuts to the master problem if the resource constraints are violated. Experimental results show the benefits of the branch-and-price-and-check approach.     

VRPSTW的混合改进蚁群优化算法*

软时间窗车辆路径问题（VRPSTW）是VRP的一种重要扩展类型,定义了其惩罚函数并建立数学模型。设计用于求解该问题的混合改进型蚁群算法并求解标准数据库中的紧时间窗实例。经过大量数据测试,获得了较好的效果,并验证了蚁群算法用于求解软时间窗车辆路径问题的成功实现。     

A tabu search heuristic for the single vehicle pickup and delivery problem with time windows

The single vehicle pickup and delivery problem with time windows is a generalization of the traveling salesman problem. In such a problem, a number of transportation requests have to be satisfied by one vehicle, each request having constraints to respect: a pickup at its origin and a delivery at its destination, and a time window at each location. The capacity of the vehicle has to be respected. The aim is to minimize the total distance traveled by the vehicle. A number of exact and approximate solution methods exists in the literature, but to the authors knowledge none of them make use of metaheuristics, still promising with other vehicle routing problems. In this paper we present tabu search and probabilistic tabu search. Results obtained on classical traveling salesman problems and a class of randomly generated instances indicate that our approach often produces optimal solutions in a relatively short execution time.     

Generalized mixed integer and VNS heuristic approach to solving the multisize containers drayage problem

This paper addresses the problem of vehicle routing in drayage operations, where vehicles can carry containers of different sizes. The multisize container drayage problem with time windows is modeled as a multiple matching problem and formulated as a mixed integer linear program (MILP) model. The proposed MILP model determines optimal pickup and delivery routes of vehicles and is applicable to any type of vehicles capable of simultaneously transporting any arbitrary number of 20‐ and 40‐ft containers. To solve larger sized problems, we proposed a variable neighborhood search (VNS) heuristic. Both MILP and VNS approaches have been tested on numerous test instances and their performances are reported.     

求解车辆路径问题的混合蚂蚁系统

研究车辆路径问题在物流配送系统中具有十分的重要意义。带时间窗车辆路径问题是每个客户的配送都有一个时间间隔限制的一类车辆路径问题。结合最大一最小蚂蚁系统、蚁群系统和最优一最差蚂蚁系统,提出求解带时间窗车辆路径问题的混合蚂蚁系统。实验结果表明：HAS能够有效地解决客户聚簇分布的带时间窗车辆路径问题。     

考虑动态平衡装卸的点对点取送货车辆路径优化

针对点对点取送货车辆路径优化问题,引入动态平衡、后进先出、三维装载等约束,以总路径最短为优化目标,构建多车多客户应用场景下的动态平衡装卸点对点取送货车辆路径优化模型;基于研究问题的特征,采用启发式插入法确定路径初始方案,设计节点交换和重新定位算子,构造路径邻域方案,并将动态平衡装卸纳入路径迭代过程,运用多重指标定序策略和三分空间策略,设计客户动态平衡装卸检算算法,并提出基于禁忌搜索的点对点取送货车辆路径优化算法,制订多车多客户取送货车辆路径方案的同时编制动态平衡装载方案。最后,通过标准算例验证方法的有效性,计算表明：所提方法能高效解决带动态平衡约束的点对点取送货车辆路径优化问题;在多车多客户应用场景下具有更强的寻优能力,求解效率更高。     

A hybrid method based on linear programming and tabu search for routing of logging trucks

In this paper, we consider an operational routing problem to decide the daily routes of logging trucks in forestry. This industrial problem is difficult and includes aspects such as pickup and delivery with split pickups, multiple products, time windows, several time periods, multiple depots, driver changes and a heterogeneous truck fleet. In addition, the problem size is large and the solution time limited. We describe a two-phase solution approach which transforms the problem into a standard vehicle routing problem with time windows. In the first phase, we solve an LP problem in order to find a destination of flow from supply points to demand points. Based on this solution, we create transport nodes which each defines the origin(s) and destination for a full truckload. In phase two, we make use of a standard tabu search method to combine these transport nodes, which can be considered to be customers in vehicle routing problems, into actual routes. The tabu search method is extended to consider some new features. The solution approach is tested on a set of industrial cases from major forest companies in Sweden.