多车型车辆路径问题的量子遗传算法研究

本文在分析现有文献中多车型车辆路径问题中车辆使用优先原则的基础上,将车辆使用费用分为固定费用和油耗费用,并建立以配送总费用最小为优化目标的数学模型。设计量子遗传算法对模型进行求解,采用量子比特位设计染色体结构,改进遗传算法中交叉与变异算子,避免优秀基因不被破坏,设计快速寻优机制与最优保留机制,增强的求解效率。最后,结合算例对模型和算法进行了检验与分析。     

基于改进模糊遗传算法的混合车辆路径问题

本文建立了多配送中心、多车型、多产品的车辆路径问题的混合数学模型,提出了一种新的模糊遗传算法求解混合车辆路径问题,通过改进的模糊逻辑控制器实现交叉概率和变异概率的动态调整,以加快算法收敛速度并避免算法陷入局部最优解。采用标准算例进行对比,证明模糊遗传算法有较好的计算结果和计算效率,并用模糊遗传算法对混合车辆路径模型进行仿真测试,取得了理想的结果。     

综合面试中的均衡分组方法

本文针对综合面试中的分组问题,首先分析了分组对综合面试结果的影响,提出了均衡分组的思想;在此基础上,提出了综合面试中的均衡分组方法,该方法构建了双目标优化模型,并开发了一个求解问题的遗传算法,该算法还可以解决一类分组问题;最后,给出算例说明方法的应用及可行性。     

物流配送中心直通配送运作时间优化研究

针对直通配送需要尽可能缩短配送中心内运作时间的问题,利用总运作时间与完成所有操作所需时间最长的货源操作时间等价的关系,构建了以最小化总运作时间为目标的配送中心内货源及目的地的出入站口指派问题模型。设计了对个体分2段进行编码、交叉和变异等操作的遗传算法,对模型进行求解,通过算例验证了模型及其算法能够对配送中心内的运作时间进行有效优化。     

基于电商承诺送达机制的多目标低碳MDVRP优化研究

针对存在多配送站的电商物流配送问题,首先,考虑实际装载量对物流配送过程中车辆燃料消耗量的影响,建立燃料消耗量模型,并结合电商平台的承诺送达机制,构建配送延迟时间函数。随后,提出了以最小化物流成本和延迟收货时间的多目标多配送站车辆路径规划问题,建立该问题的混合整数规划模型。再次,采用基于分解的多目标遗传求解算法对问题进行求解。该算法采用矩阵编码的方式,设计了基于贪婪搜索策略的启发式初始化方法,考虑到贪婪搜索策略容易陷入局部最优的劣势,在算法迭代过程中,允许部分不可行解存在以扩大解空间的搜索范围,并进一步设计了遗传算法的交叉和变异算子。最后,以具体物流配送案例进行数值实验,实验结果表明所设计的算法对求解本文模型是有效的。     

多枢纽轴辐式协同物流网络任务-路径优化匹配研究

针对物流网络运营中规模效益低、运营商与客户利益冲突等问题，本文提出了基于多枢纽轴辐式协同物流网络的任务-路径优化匹配策略。在网络结构确定的条件下，从物流集成服务商角度出发，综合考虑资源发车时刻、路径能力限制、动态成本折扣系数以及任务延时惩罚，构建了以总物流成本最小和时间最短为优化目标的轴辐式协同物流网络任务-路径优化匹配数学模型。根据问题特点，设计了基于三层编码的遗传算法对模型进行求解，同时配合多点交叉、变异机制提高求解效率。研究结果表明，集并运输能够大幅度降低任务集执行成本，但当集并带来的交货延迟、客户满意度降低等负面效应超过其正面效应时，需适当匹配直达线路以提高整体效益。     

回载可分的闭环供应链多配送中心多车辆运输策略

本文从车辆路径的角度研究了具有多个配送中心、多台车辆结合前向物流配送和逆向物流回载的闭环供应链运输策略,考虑回收产品的不同形态和可分批运输的特点,引入库存限制和成本惩罚,建立并分析了问题的数学模型.运用sweep算法把多配送中心转化为单配送中心,引入2σ原则构造了分组的启发式求解方法.算例分析表明该策略的合理有效性.     

基于联合配送的开放式动态车辆路径问题及算法研究

针对跨区域多配送中心多车型开放式动态联合配送问题,通过引入时间轴概念将动态问题转化为静态问题,建立考虑车载率的开放式车辆路径模型,提出多配送中心问题的整体算法和多车型的使用原则,强化物流资源整合和跨区域路径整体优化.利用云模型中云滴的随机性与稳定倾向性,改进遗传算法中交叉与变异概率的设置方式,采取“初始优化+实时优化”的两阶段求解策略,对开放式动态车辆路径问题进行实时再优化.最后,结合算例对模型和算法的有效性进行验证.     

时变路网下多中心电动车-无人机协同配送路径优化

针对车辆行驶时间依赖配送区域路网速度变化的多中心电动车-无人机协同配送路径问题,本文综合考虑配送区域路网交通信息,无人机最大飞行距离、承重能力,配送过程中电动车电池的荷电状态,以及车辆行驶速度、载重量等对电动车能耗的影响等,以总配送成本最小化为目标建立多中心车辆-无人机协同配送路径优化模型。根据问题特征,本文设计遗传大邻域搜索混合算法求解模型,该算法在传统遗传算法基础上,采用整数编码随机生成初始种群,通过无人机最大承重能力、飞行距离筛选无人机可服务的客户,然后确定车辆及无人机的配送路径生成初始解,并嵌入2组摧毁和重建算子进行进化操作。本文通过多组算例验证了算法及模型的有效性,并分析了车辆搭载的无人机数量以及车辆行驶速度对配送方案制定的影响。研究成果丰富和拓展了车辆路径优化的研究领域,可为交通、物流企业优化决策配送方案提供理论依据。     

时间依赖型多配送中心带时间窗的开放式车辆路径问题研究

本文研究了时间依赖型多配送中心带时间窗的开放式车辆路径问题,基于道路通行情况,建立车辆行驶速度时间函数;考虑车辆载重、里程限制与客户点服务时间窗的约束,建立混合整数规划模型,目标函数为最小化车辆总成本,具体包括车辆行驶时间成本和车辆固定发车成本;提出了一种二维编码方式的混合遗传算法,针对混合遗传算法设计了多分区段单点交叉策略、动态插入算子及局部搜索策略;最后,基于Solomon VRPTW基准数据集生成27个测试算例,使用混合遗传算法进行求解。数值实验结果表明,考虑道路通行情况,选择合理的出发时间,避免拥堵时段进行配送服务,能明显减少车辆的总行驶时间,且验证了混合遗传算法能够获得问题的满意解。     

求解带时间窗的装-卸载问题的概率式禁忌搜索算法

本文介绍一个求解有时间窗的装载—卸载问题的概率式禁忌搜索算法。论文首先回顾了求解VRP、PDP问题的主要方法,介绍了搜索算法的基本概念,给出了基于概率式禁忌搜索的详细算法。初步实验表明新算法优于传统禁忌搜索算法。     

A metaheuristic for the delivery man problem with time windows

Journal of Combinatorial Optimization - The Delivery Man Problem with Time Windows (DMPTW) is an extension of the Delivery Man Problem. The objective of DMPTW is to minimize the sum of...     

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.     

蓄冷式多温集配路径优化模型

现实中,由于配送中心选址对占地面积、土地成本等要求较高,加之物流企业资金有限或交通拥堵等限制,配送中心的设置通常会远离市中心。为了减少集货与配送车辆往返配送中心的次数以及车辆行驶距离,本文以总成本最小化,包括车辆派遣成本、行驶成本、碳排放成本、违背时间窗的惩罚成本、保温柜/箱成本、非整箱货物的配送成本,构建了1个配送中心由大型车辆为m个供应商采用蓄冷柜/蓄冷箱集货,由1个虚拟接驳点(中型车辆)结合小型车辆为n个零售门店采用蓄冷箱多温共配的路径优化模型,并设计了基于蚁群算法的混合更新信息素策略。以20个零售门店与6个海鲜供应商的三种品温海鲜品为仿真算例,验证了模型的有效性。实例分析发现：引入虚拟接驳点的配送线路数低于单纯的配送线路数;时间窗限制越宽松,引入虚拟接驳点的优越性越突出;具有虚拟接驳点的多温集配总成本低于自配送中心的集配总成本;具有虚拟接驳点的蓄冷式多温集配尤其利于低碳环保的冷链系统构建。     

多车场带时间窗车辆路径问题的变邻域搜索算法

多车场带时间窗车辆路径问题是车辆路径问题集合中的一个极为复杂、且仍未得到较好解决的问题。针对这一问题,建立了它的整数规划数学模型,提出了一种改进型变邻域搜索算法。该算法在初始解的构造阶段采用聚类方法完成客户的分配,运用混合算子进行局部搜索,通过后优化过程增强寻优效果,引入模拟退火模型对新解的接受进行控制。最后,在Cordeau提出的标准用例上对改进型变邻域算法进行了实验,实验结果更新了大部分目前该问题的最优解,并在算法的稳定性和求解时间上体现出一定优势。实验表明,该算法是一种求解多车场带时间窗车辆路径问题的有效方法。     

Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements

Inspired by a problem arising in cash logistics, we propose the Capacitated Routing Problem with Profits and Service Level Requirements (CRPPSLR). The CRPPSLR extends the class of Routing Problems with Profits by considering customers requesting deliveries to their (possibly multiple) service points. Moreover, each customer imposes a service level requirement specifying a minimum-acceptable bound on the fraction of its service points being delivered. A customer-specific financial penalty is incurred by the logistics service provider when this requirement is not met. The CRPPSLR consists in finding vehicle routes maximizing the difference between the collected revenues and the incurred transportation and penalty costs in such a way that vehicle capacity and route duration constraints are met. A fleet of homogeneous vehicles is available for serving the customers. We design a branch-and-cut algorithm and evaluate the usefulness of valid inequalities that have been effectively used for the capacitated vehicle routing problem and, more recently, for other routing problems with profits. A real-life case study taken from the cash supply chain in the Netherlands highlights the relevance of the problem under consideration. Computational results illustrate the performance of the proposed solution approach under different input parameter settings for the synthetic instances. For instances of real-life problems, we distinguish between coin and banknote distribution, as vehicle capacities only matter when considering the former. Finally, we report on the effectiveness of the valid inequalities in closing the optimality gap at the root node for both the synthetic and the real-life instances and conclude with a sensitivity analysis on the most significant input parameters of our model.     

动态需求下车辆路径问题的周期性优化模型及求解

针对客户点不断更新的动态需求车辆路径问题,依据滚动时域对配送中心工作时间进行划分,提出基于延迟服务的周期性客户点实时重置策略,策略中延迟服务机制能结合车辆启动延迟系数对照当前时域的时间进行检验,满足所有客户点的服务需求,保证车辆满足中心时间窗约束。设计多阶段求解的混合变邻域人工蜂群算法对各时间片内子问题进行连续迭代优化,算法中子路径动态转变的设计能较好平衡原有客户点和新客户点对路径更新和车辆实时信息匹配的要求。算例验证及对比分析表明本文策略和算法在求解动态问题时的有效性和可行性。     

突发性片堵塞下两车信息共享的加拿大旅行者问题

提出突发性片堵塞下两车信息共享的加拿大旅行者问题,即两车欲从起点出发去终点,在运输过程中会遭遇突发性片堵塞,若两车对堵塞信息都能有限预知且车辆间可以信息共享,如何制定路径选择策略使两车花费的总时间尽可能少。针对该问题,采用在线问题与竞争策略的理论和方法,建立突发性片堵塞下两车信息共享的在线路径选择模型,设计混合贪婪策略,结合片堵塞中多条路段同时发生堵塞的特点,以及所选路径是否经过信息预知点到片堵塞起始点的路段（预知路段）等策略不同情形的分析,证明混合贪婪策略竞争比。最后进行实例分析,验证模型和策略的有效性。     

Online pickup and delivery problem with constrained capacity to minimize latency

The online pickup and delivery problem is motivated by the takeaway order delivery on crowdsourcing delivery platform, which is a newly emerged online to offline business model based on sharing economy. Considering the features of crowdsourcing delivery, an online pickup and delivery problem with constrained capacity is proposed, whose objective is to route a delivery man with constrained capacity to serve requests released over time so as to minimize the total latency. We consider online point-to-point requests with single pickup location where each request has to be picked up at the single pickup location and delivered to its destination, and each request become available at its release time, which is not known in advance. The lower bound of this problem for various capacities is proved. Two online algorithms WR and WI are presented, the competitive ratios on a half line and on general metric space are proved respectively. Further, a computational study is conducted to compare the performance of these two online algorithms on random instances of general metric space. The result shows algorithm WR performs better than WI in random cases but not in the worst case.

     

考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究

在政府政策大力支持以及社会环境意识不断增长的背景下,电动汽车在物流配送行业快速普及。电动汽车参与的物流配送服务需要物流专员、电动汽车和顾客三方协作完成。因此,在传统车辆配送路径优化的基础上,车辆的多样性、充电策略、人车的匹配以及服务时间差异化等因素都会影响物流运营成本。本文提出了考虑差异化服务成本的多车型电动汽车路径优化与充电策略问题并建立了该问题的整数规划数学模型。其次,提出了混合启发式算法MCWGATS,并通过多组算例验证了算法的有效性。最后,采用多组算例分析了多车型和差异化服务时间对运营成本的影响。实验结果表明,该模型有助于物流企业提高人员、物流车辆、服务时间等资源的利用效率,降低运营成本。