以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

时变单车路径优化模型及动态规划算法

车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而,在已有的研究文献中,车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解,本文提出了一种贪婪补货策略压缩原问题解空间,设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短,并在车辆装载能力超过所有客户配送总需求时实现最短配送时间,即,使用较大装载能力车辆能节约更多配送时间。     

包含随机客户的选择性旅行商问题建模及求解

针对快递配送过程中客户需求具有不确定性的特征,提出一种新的路径优化问题——包含随机客户的选择性旅行商问题,在该问题中客户每天是否具有配送需求存在一定概率,并且对客户进行配送可获取一定利润。同时考虑以上两种因素,建立该问题的数学模型, 目标为在满足行驶距离限制的条件下,找出一条经过部分客户的预优化路径,使得该路径的期望利润最大。其可用于模拟构建最后一公里快递配送的路径问题,提供更具有经济效益的配送路径。随后提出包含精细化局部搜索策略的改进遗传算法,算法根据问题特点构建初始可行解。最后通过多个计算比对结果表明,该算法具有较高的计算效率。     

近似动态规划求解随机需求分批配送车辆路径问题

本文针对现实生活中固体废弃物收集等需求随机的分批配送车辆路径问题，建立双层马尔科夫决策模型，使用基于动态分区的全局修正策略和基于部分重优化算法的近似动态规划进行求解。通过算例测试和分析表明模型和算法的有效性。得到以下结论：1)SDVRPSD的最优解中车辆数略高于最小期望车辆数的1.2倍，接近使用进化算法得到的最优解中的车辆数，这两者平均约相差0.6辆。2)与静态分区相比，动态分区以花费较多时间为代价，能显著提升服务范围、降低服务费用，并增加分批配送点数量。3)算法最优解与使用固定路径算法得到的初始解相比，期望服务需求量平均提高约2.6%,期望行驶费用平均降低约1.9%;分批配送点数平均多2.5个。     

一种基于双链量子编码的动态车辆路径问题解决策略

针对配送调度事件动态变化的动态车辆路径问题(DVRP), 以最小化运输成本、最小化配送时间 与最大化载货率为目标, 建立了问题的数学模型,提出了改进的多相量子粒子群算法. 针对DVRP问题的特点,提出基于车辆链和货物链的双链量子编码方法; 同时设计了基于周期和 重调度因子驱动的动态调度策略. 最后将方法应用于动态仿真算例, 并与其他经典算法比较, 结果验证了所提出方法的有效性.     

求解硬时间窗约束下随机需求库存-路径问题的优化算法

随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem, SDIRP)即考虑随机需求环境下供应链中库存与配送的协调优化问题,是实施供应商管理库存策略过程中的关键所在,也是典型的NP难题之一。文章以具有硬时间窗约束的随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem with Hard Time Windows, SDIRPHTW)为研究对象,将SDIRPHTW分解为直接配送的随机库存-路径问题和具有硬时间窗约束的路径优化问题两个子问题,并以最小化系统运行成本和用车数量为目标,设计了一个基于(s,S)库存策略和修正C-W节约法的启发式算法。最后,通过相应的数值算例验证了算法的有效性。     

基于客户信用度的物流配送车辆路径问题研究

针对当前城市物流配送过程中普遍存在的客户中途取消订单、无故退换货等交易违约问题,引入客户信用度的测度方法。根据客户历史交易违约数据计算客户信用值,并转化求解客户信用度,构建了包含车辆配送成本、租赁成本以及违反时间窗惩罚成本的配送路径优化模型。设计了一种遗传(GA)-禁忌搜索(TS)混合算法进行模型求解,在算法过程中应用精英保留策略进行循环迭代寻优。结合重庆某外卖物流配送网络的实例数据,验证了模型和算法的有效性和可行性。实验结果给出了不同服务策略下的物流配送调度方案,并进行了基于客户信用度的客户配送服务序列调整比较和敏感度分析。研究表明客户信用等级的合理划分可以有效降低物流配送成本和提高客户服务水平。     

带客户协同分仓的动态车辆路径问题研究

随着互联网商业迭代的不断深化,越来越多的企业倾向于从商品前置视角解决配送距离与配送时效性的矛盾。为此,本文研究基于客户协同分仓备货的动态车辆调度问题(Dynamic Vehicle Routing Problem with Inventory Synergetic Customer, DVRP-ISC),设计考虑区域分异特征的协同分仓客户选择方法,建立多阶段动态配送网络优化模型。鉴于研究问题的特殊性,设计多阶段两级网络协同配送路径优化算法;最后,以仿真算例、自定义算例集和基准算例,验证所提模型和算法性能及其拓展性。     

基于预判发货的网络零售商双模式批量配送研究

基于预判发货的背景,考虑订单处理中心和配送站之间存在第三方物流和自营物流两种配送模式,研究了B2C网络零售商的动态批量配送问题。首先利用混合整数规划构建了一个三级供应链系统下的动态批量配送模型,接着采用网络流规划的技术重新建模,并在其基础上对最优解的性质进行了分析,进而设计了计算时间复杂度为O(T²)的精确动态规划求解算法。最后用算例实验验证了该算法的有效性和适用性。     

考虑完全拆分的拣选分批与拣选路径集成优化模型

在电商海量订单背景下,在线订单拣选作业难度加大,因此设计了基于订单完全拆分的拣选分批与拣选路径综合优化模型解决此问题.模型共分两阶段.第一阶段,基于种子算法,设计考虑订单完成度、等待时间与拣选路径的拣选分批模型;第二阶段以拣选单流为单队列,设计多拣选员并行服务的拣选系统.行走策略为基于返回型和遍历型的综合策略,拣选路径优化模型采用模拟退火算法求解.算例分析表明,与传统的不拆分拣选分批模型相比,构建的综合优化模型能够显著提高拣选系统效率.拣选员为4人时,模型能够使总服务时间减少58.79%,订单完成率提高10.09%.     

面向电商终端物流配送的电动车配置与路径集成优化

在电子商务终端物流配送方面,存在能力与需求的矛盾。一方面,电动车存在货物容量约束和电池电量约束,配送能力有限;另一方面,一个物流配送点需要为众多的消费者进行门到门的配送,配送任务繁重。针对电子商务环境下终端物流配送规模大、电动车货物容量和行驶里程有限的问题,建立电商终端物流配送的电动车配置与路径规划集成优化模型,并提出一种基于临近城市列表的双策略蚁群算法,实现物流配送电动车辆配置与配送路径集成优化。该模型以电动车辆数最少和总路径最短为目标,以电动车货物容量和电池续航里程为约束,是带容量的车辆路径问题的进一步扩展,属于双容量约束路径规划问题。双策略蚁群算法在货物容量和续航里程的约束下,将蚁群搜索策略分为两类,即基于临近城市列表的局部搜索策略和全局搜索策略,在提高搜索效率的同时防止陷入局部优化。最后,通过阿里巴巴旗下菜鸟网络科技有限公司在上海的30组真实配送数据进行了测试,验证双策略蚁群算法显著优于一般蚁群算法。     

改进蚁群算法优化周期性车辆路径问题

周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T＞1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。     

智能网联下无人车配送路径优化

结合智能网联无人车实时信息共享与路径选择的特点,研究其配送路径优化问题。通过引进关键点更新策略,制定路径预规划阶段和路径实时调整阶段无人车路径选择策略,提出智能网联环境下基于实时交通信息的车辆路径问题两阶段模型。其中,路径预规划阶段模型确定初始路径与每辆车服务的客户点,路径实时调整阶段模型对每辆车的路径实时调整。对于该优化模型设计遗传算法进行求解,并通过算例验证了模型与算法的可行性。研究结果表明,本文构建的无人车配送优化模型,有效的结合了无人车实时通信与路径选择的特点,节省了无人车配送时间。研究对于无人车在第三方物流配送领域的推广应用具有一定的探索意义。     

校车站点及线路的优化设计

以高校新校区教师校车站点及线路安排为对象,首先针对乘车站点建立了双目标非线性规划模型,其中目标函数包括乘客到达站点的距离偏差最小与所有乘客到达站点的总的距离最小两个方面;站点确定后针对车辆数最少、车辆行驶的总距离最短、各辆车的运行距离均衡及各辆车的负荷均衡这4个目标建立针对线路优化的多目标非线性规划模型,并给出了解决这类问题的启发式优化算法.与目前国内外研究相比较,该模型与算法更实际,更具体的给出了问题的解答.     

基于两阶段求解策略的动态电动车辆路径优化研究

由于政府对新能源汽车的补贴政策和市区对燃油车限行政策的实时,越来越多的物流公司在城市配送中广泛采用电动汽车。然而,电动车续航里程受限,需要在途充电或者换电,同时客户需求的动态性以及充/换电设施的排队等现实因素也应该被考虑。为此,提出了分阶段策略求解动态电动车辆路径优化问题,并建立了两阶段的EVRP模型。其中第一阶段针对静态客户建立了静态EVRP模型,第二阶段在设计了换电站及动态客户插入策略的基础上,建立了动态EVRP模型以路径更新策略。最后,设计改进的CW-TS混合启发式算法来求解静态模型,设计贪婪算法求解动态模型。实验结果表明,模型与算法具有较好的适用性和有效性。     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

求解车辆路径问题的离散蝙蝠算法

根据车辆路径问题的数学模型,分析了它的具体特征,从而对BA的操作算子又进行了重新定义,设计了求解VRP问题的离散蝙蝠算法,并通过实例测试将离散蝙蝠算法与其他算法进行比较,验证了该算法求解VRP问题的有效性与可行性.     

随机需求的车辆路线问题的新模型

本主要研究随机需求的VRP问题,其中服务需求量满足二项式分布,根据期望值的大小我们提出了在一条路线上理想最大服务点数的新概念,并在此基础上建立了三种VRP问题的新模型,由于允许服务失败两次和部分服务使得模糊能适应多种实际问题,以模拟退火思想为基础的两阶段方法经修正后用于解新模型并取得较好的数值结果,理论分析和数值结果表明,新模型较好地描述随机需求的VRP问题,并且容易求解。     

车辆路径问题的混合优化算法

讨论了一类车辆路径调度问题(VRP)及其数学模型，并且分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作，然后结合2-opt局部优化算法提出了GA with2-opt算法来求解VRP问题，试验结果说明了该算法的有效性和可行性。