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

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

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

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

低碳环境下的车辆路径问题及禁忌搜索算法研究

基于节能减排的新视角,本文研究了低碳环境下由第三方提供运输服务的车辆路径问题,在安排车辆路径时,同时考虑了能耗、碳排放和租车费用,而这些费用不仅与距离有关,也与客户点的需求量和车辆速度有关。提出了考虑车辆运量和速度的能耗计算方法,建立了非满载运输方式下的低碳路径模型——LCRP。设计了基于路径划分的禁忌搜索算法RS-TS对问题进行求解,该算法引入了一种新颖的路径编码与解码算法WSS,采用了三种邻域搜索方法。通过基准测试实例验证了算法能有效地找到满意解,并揭示了距离、能耗、行驶时间等参数之间的关系,实验分析表明采用低碳路径安排更加经济环保且选择中低的交通速度更有利于节约能耗和降低碳排放。     

有顾客时间窗和发货量变化的紧急车辆调度研究

对紧急车辆调度系统进行了研究,探讨了紧急车辆调度问题实现的关键技术.对有顾客时间窗和发货量变化的紧急车辆调度问题,运用了禁忌算法(TS)进行优化.算法基于实数编码,应用GENI插入法产生初始解和进行邻域操作,设计了三种邻域,利用容量约束控制单条路径配送点数,采用惩罚函数处理时间窗约束,通过设计虚拟车场等方法实现了车辆的紧急调度.本文给出了一个具有代表性的算例试验结果,算例结果及其分析表明了此方法对优化紧急车辆调度问题的有效性.     

考虑自取服务和门到门服务的电动汽车物流网络优化策略研究

在环境意识增长与政府政策支持的有利条件下,电动汽车在物流领域得以快速发展。为提高物流服务的效率,降低企业运营成本,文中研究了考虑顾客服务策略的电动物流汽车服务设施选址与配送路径问题。采取顾客自行取货与配送人员送货上门相结合的多样化服务策略,使得服务站点的建设成本、顾客点配送路径成本以及服务站点补货路径成本之和最小。建立了整数规划数学模型,允许配送车辆在服务过程中前往服务站点接受充电服务。其次,提出了基于改进节约算法和禁忌算法的混合启发式算法MCWSA-TS。随后,在小规模算例将CPLEX运算结果与MCWSA-TS进行对比,证明了算法的有效性。最后,采用多组算例探讨了顾客取货半径对运营成本的影响,并对分离配送策略与联合配送策略进行对比分析。实验结果表明,多样化服务策略有助于企业满足顾客取货时间和取货方式的个性化需求。同时,兼顾运营成本与顾客满意度,促进电动汽车参与的物流服务快速发展。     

多车次同时集散货物路线问题研究

研究了配送车辆数和车辆工作时间内有限的多车次同时集散货物路线问题,以车辆数和运输里程最小为目标建立了多目标模型,提出了允许不可行解的禁忌搜索法.该方法能同时解决路线安排和路线分配的问题,其中路线安排采用了4种邻域搜索方法和重起策略,路线分配采用了初次分配和二次调整策略.算例分析表明,该方法能有效地找到满意解,且采用多车次安排路线比单车次安排路线更加经济合理.     

基于风险的考虑成本和允许等待的车辆运输调度问题研究

本文同时考虑了成本约束和允许等待情形,研究了最小化风险的车辆运输调度问题,其中运输风险是随时间不同而变化的,即研究在时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的顶点上决定的出发和等待时间的综合问题。建立了相应的混合整数规划模型,设计了相应的算法,并分析了算法复杂性,最后通过算例验证了该算法的有效性和可行性。     

电子商务下基于改进两阶段算法的有时间窗车辆调度优化

为满足电子商务下的物流配送需求,将传统车辆调度模型进行修改,将目标函数改为基于费用最小,在约束条件中增加时间约束、货物容积约束、车辆最大工作时间、多种车型、载重量限制和最大行驶距离等,以提高模型的适用性和通用性。由于有时间窗的车辆调度问题是NP难问题,采用改进两阶段算法进行求解。即第一阶段用模糊分层聚类法将客户群分成若干区域,在每个区域又用扫描算法分解成若干符合约束条件的小规模子集;第二个阶段对各个分组内客户点,就是一个个单独TSPTW模型的线路优化问题,因此,采用改进混合遗传算法进行优化求解,最后的算例仿真表明了算法的有效性和可行性。     

基于模糊时间窗的车辆调度问题研究

基于现实生活中配送企业车辆资源有限和顾客对服务时间要求并非完全刚性的特征,通过时间窗模糊化处理将顾客服务的满意度量化为配送服务开始时间的模糊隶属度函数。在一定满意度下,构建了基于模糊时间窗的车辆调度模型,根据模型的特点,改进了基于客户的染色体编码方式,设定了一种新的约束处理方法,避免了惩罚策略中选取惩罚因子的困难。在算法中用模糊优化程序处理问题的模糊特征,通过对顾客服务时间的局部调整来确定最佳服务时间。最终通过实例验证与原结果比较发现,引用模糊时间窗函数不仅可以降低配送成本,而且有利于节省运力资源。     

供应网络中越库转运中心仓门分配问题研究

本文探讨一种带有时间窗口的仓门分配问题--车辆在转运中心进行货物装却作业时如何在其时间窗口限制内有效的分配有限的仓门资源,以达到最佳运作效率.以往的研究结果表明该问题是强NP难题,因此本文针对该问题的特殊结构,提出一种新颖的整合了贪婪算法、遗传算法以及禁忌算法思想的混合启发式算法来有效的解决该问题.我们并将该混合启发式算法与遗传算法、禁忌算法以及CPLEX这三种方式的求解效果进行对比,其数值实脸结果表明混合启发式算法在求解效果上有明显的优势.     

一个单件车间生产作业计划优化模拟系统

针对中小批量单件车间生产作业计划生成与再生问题,集成Visual Foxpro5.0与Siman 3.51开发了一个系统原型,包括模拟模型生成器、时间参数推算器和禁忌搜索算法。用模拟模型生成器得到一个比较详细的中小批量单件车间生产作业计划方案,以此为初始可行解,再用时间参数推算器和禁忌搜索算法进行优化,得到一个优化了的车间生产作业计划方案。实验表明,本系统较好地解决了中小批量单件车间生产作业计划生成问题。     

Tabu search for the real-world carpooling problem

Carpooling is a flexible shared transportation system which can effectively reduce the vehicle numbers and fuel consumption. Although many carpooling systems have been proposed, most of them lack practicality, veracity, and efficiency. In this paper, we propose a new useful variant model of the long-term carpooling problem which involves multiple origins and one destination. Such problems commonly occur in a wide number of carpooling situations in real-world scenarios. Our work is motivated by the practical needs to solve environmental pollution, parking problems, traffic jams and low utilization of resources. A Tabu search algorithm is proposed in this paper to solve the carpooling problem. The proposed algorithm aims at a wide range of passenger distribution and routing problems. The computational results based on real world user data show the effectiveness of the proposed algorithm. Moreover, we developed a mobile application based on our carpooling model.     

车辆路径问题的禁忌搜索算法研究

论文在对车辆路径问题进行简单描述的基础上,通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法,并进行了实验计算。计算结果表明,用本文设计的禁忌搜索算法求解车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。     

Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery

Today manufacturers have become much more concerned with the coordination of both manufacturing (of new products) and recycling (of reusable resources) operations. This requires simultaneous scheduling of both forward and reverse flows of goods over a supply chain network. This paper studies time dependent vehicle routing problems with simultaneous pickup and delivery (TD-VRPSPD). We formulate this problem as a mixed integer programming model, where the time step function is used to calculate the travel time. To efficiently solve this complex problem, we develop a hybrid algorithm that integrates both Ant Colony System (ACS) and Tabu Search (TS) algorithms. Our algorithm uses the pheromones, travel time and vehicle residual loading capacity as a factor structure according to the characteristics of TD-VRPSPD. In our computational experiments, 56 groups of benchmark instances are used to evaluate the performance of our hybrid algorithm. In addition, we compare the performance of our hybrid algorithm with those of individual ACS and TS algorithms. The computational results suggest that our hybrid algorithm outperform stand-alone ACS and the TS algorithms.     

Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics

This paper addresses a periodic vehicle routing problem encountered in home health care (HHC) logistics. It extends the classical Periodic Vehicle Routing Problem with Time Windows (PVRPTW) to three types of demands of patients at home. Demands include transportation of drugs/medical devices between the HHC depot and patients׳ homes, delivery of special drugs from the hospital to patients, and delivery of blood samples from patients to the lab. Each patient requires a certain number of visits within a planning horizon and has a set of possible combinations of visit days. Daily routing should meet time window constraints associated with patients, the hospital and the lab. The problem consists in determining the visit days of each patient and vehicle routes for each day in order to minimize the maximal routing costs among all routes over the horizon. We propose a Tabu Search method combined with different local search schemes including both feasible and infeasible local searches. The proposed approaches are tested on a range of instances derived from existing Vehicle Routing Problem with Time Window (VRPTW) benchmarks and benchmarks on special cases of our problem. Numerical results show that local search scheme starting with an infeasible local search with a small probability followed by a feasible local search with high probability is an interesting hybridization. Experiments with field data from a HHC company show that the proposed approach reduces the total cost and better balances the workloads of vehicles.     

A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries

The vehicle routing problem with pickups and deliveries (VRPPD) extends the vehicle routing problem (VRP) by allowing customers to both send and receive goods. The main difficulty of the problem is that the load of vehicles is fluctuating rather than decreasing as in the VRP. We design a reactive tabu search metaheuristic that can check feasibility of proposed moves quickly and reacts to repetitions to guide the search. Several new best solutions are found for benchmark problems.     

Multi-depot vehicle routing problem with time windows under shared depot resources

A new variant of multi-depot vehicle routing problem with time windows is studied. In the new variant, the depot where the vehicle ends is flexible, namely, it is not entirely the same as the depot that it starts from. An integer programming model is formulated with the minimum total traveling cost under the constrains of time window, capacity and route duration of the vehicle, the fleet size and the number of parking spaces of each depot. As the problem is an NP-Hard problem, a hybrid genetic algorithm with adaptive local search is proposed to solve it. Finally, the computational results show that the proposed method is competitive in terms of solution quality. Compared with the classic MDVRPTW, allowing flexible choice of the stop depot can further reduce total traveling cost.