本发明属于车辆路径优化，涉及一种面向大规模客户的末端配送路径优化方法。
背景技术：
1、随着物流行业的迅猛发展，使用外卖、跑腿和同城配送等的用户日益增多，尤其在互联网技术日趋成熟下，人们更倾向于网上购物、点餐。
2、而在突发状况下，大量线下业态陷入停摆状态，促使各行各业积极拥抱线上化。供给端的结构性变化与需求端的结构性变化与习惯的养成使得线上下单，线下送达模式已然成为新常态；与此同时，城市化进程持续推进，末端即时消费在内的新消费理念与模式将日渐普及。
3、而在末端服务的所有环节中，末端配送环节是直面消费者开展服务的环节。首先末端配送种类多，批量少，频次高，订单越来越碎片化，使得城市末端配送的频次不断升高；其次，由于大规模末端配送存在着客户点分散，货物信息不确定的特点，使得快递末端配送始终存在配送成本高、配送效率低下等问题。而末端配送一般是由商户的配送员凭主观感觉选择配送路线和取货路线，导致了配送路线规划不合理，此外，由于上述配送存在的问题，会导致客户的配送服务满意度下降，会间接影响客户对于商户的购买欲，对于面向大规模客户的末端配送路径优化是目前待解决的问题。
4、在车辆路径优化领域，车辆路径问题(vrp)的研究主要集中在问题建模上和求解算法上，如带容量约束的vrp(capacitated vrp，cvrp)、带时间窗约束的vrp(vrp withtime windows，vrptw)、多车型vrp(heterogeneous vrp，hvrp)、多车场vrp(multi-depotvrp,mdvrp)、时间依赖型vrp(time-dependent vrp，tdvrp)、绿色vrp(green vrp，gvrp)、动态vrp(dynamic vrp，dvrp)等。其中除了动态vrp问题是解决实时需求信息外，其他vrp问题的需求信息都是提前获知的，运用了启发式算法进行路线规划，这会导致可能无法运用到真实的末端配送情形下。实际情况下，大规模客户末端配送的信息，都是实时不同时间段产生的，所以需要动态算法来进行研究；在现实的末端配送服务中，配送人员需要在城市道路中反复地进行取送货来满足实时订单的需求。将这种需要车辆需要在有大规模实时订单增加的情形下进行取送货，并且以服务完所有订单的总时间最小为优化目标的问题描述为末端取送货路径优化问题。现已有的成果大多没有考虑到末端客户的需求是具有实时性和不确定性的。
技术实现思路
1、有鉴于此，本发明的目的在于提供一种面向大规模客户的末端配送路径优化方法，针对现实生活中的大规模客户订单配送问题，末端配送车辆需要返回配送起点取货的情形，设计了针对大规模客户订单得动态算法，来求得最佳的车辆配送路线，以解决大规模客户的末端配送路径优化问题。
2、为达到上述目的，本发明提供如下技术方案：
3、一种面向大规模客户的末端配送路径优化方法，具体包括以下步骤：
4、s1：针对客户订单的实时性和配送车辆需要返回配送起点取货的实际配送场景，构建面向大规模客户的实时取送货路径优化问题；
5、s2：构建以总订单配送时间最小化为目标的末端客户实时订单路径优化模型，并对优化模型的目标函数设定约束条件；
6、s3：针对配送过程中客户新增的实时订单，采取末端实时订单的滚动时域算法，为配送车辆设计贪婪算法和w&i(wait and ignore，等待时忽略订单服务)算法，以此来分配实时新增的订单，并根据其动态算法形成的一组实时订单序列位置生成初始解，再利用遗传算法(ga)解得配送车辆最佳配送路线。
7、进一步，步骤s1中，构建面向大规模客户的实时取送货路径优化问题，具体包括以下步骤：
8、s11：给定一个网络图g；
9、s12：假设所有需要配送的订单点ri＝(ti,li)随机分布在此网络图g上，将其组成的订单序列记为n表示所出现的订单数量，ri＝(ti,li)表示订单ri在ti时刻距离配送起点li处释放，由于现实情形下的道路是存在转向限制的，因此该网络图g由不同的节点ki相互连接，为订单ri的后继可转向节点，即订单ri在以当前方向在节点间移动时，当前位置和方向的下一个可转向节点，ki表示订单ri只能在距配送起点处进行转向和掉头；
10、s13：假设每一个订单出现之后，配送车辆必须从配送起点取货才能配送已出现的该订单；零时刻时配送车辆在配送起点，之后会以单位速度出发，前去配送出现的订单，订单序列中所有订单都必须被配送，配送完所有订单后要求配送车辆返回配送起点；
11、所有车辆以均匀速度行驶；不考虑订单的制作时间，当配送车辆经过需求点时，即认为该需求已得到服务。
12、进一步，步骤s2中，构建的末端客户实时订单路径优化模型的总优化目标函数为：
13、
14、式(1)是目标函数，表示平均每个订单的完成时间，是当订单需求实时出现时，考虑完成所有订单平均时间和有转向限制性的配送网络建立即时配送模型；
15、式(1)中，o＝{o1,o2,...,oi}表示订单的序列；n＝{n0,n1,n2,…,ni}表示所有节点集合，其中i＝0表示配送中心，i＝1,2,...,n表示所需服务的订单点的下一个可转向节点，表示订单的信息，其中ri表示订单的释放时间，di表示订单i的坐标，表示释放需求时的时刻时间；
16、对优化模型的目标函数设定的约束条件为：
17、
18、
19、
20、
21、
22、
23、
24、
25、
26、
27、
28、
29、
30、
31、
32、
33、以上约束条件中：k表示第k个配送员，k∈k，k表示配送员数量；xijk表示是否由第k个配送员在第i条路径配送订单j，是为1否则为0；dij表示从上一服务完节点到i下一订单j的载重；q表示配送员的配送容量限制，每个客户的需求量为1；si表示从上一服务完节点到i下一订单j的载重；表示到达取货点的时间；表示到达客户节点的时间；m表示一个足够大的正数；表示订单oi的实际送达时间；ti表示订单oi的实际取货时间；i表示订单i的集合；t∈t表示当前时间t，将其离散化，t表示当前时间的集合；lij表示节点i到j的距离
34、式(2)表示所有路径中每个订单必须被服务且只被服务一次；
35、式(3)表示整个离散时间内，每个订单必须被服务一次；
36、式(4)表示配送员在每个时刻的配送容量限制；
37、式(5)表示在所有配送路径中，配送员只能选择其中一条配送路径；
38、式(6)表示只有当订单分配给配送员，订单才会出现在路径上；
39、式(7)和式(8)表示配送员在配送过程中可在起点等待，故每个订单的取货时间和送达时间不小于配送员行进到取货点和客户节点的最早时间；
40、式(9)表示当第k条路径被选中时，yik的值在订单j的服务时间段内都取1；
41、式(10)和式(11)表示每个订单的取货时间必早于其送达时间，且必晚于其释放时间；
42、式(12)表示订单的实际送达时间不能早于其释放时间；
43、式(13)表示当前时间必须在订单oi取货后且送至客户前，即满足变量才会取1；
44、式(14)表示在非对称网络结构中，节点i，j之间的距离可能不相等；
45、式(15)和式(16)表示订单的下一个节点一定是ni；
46、式(17)为决策变量约束；其中决策变量如下：表示第j个配送员是否在第k条路径上访问了第i个订单，如果是，那么反之则为0；xit表示配送员在t时刻是否正在服务订单oi，若是，xit＝1，反之为0。
47、进一步，步骤s3中，所述滚动时域算法具体是将问题分成多个时间段，每个时间段只考虑部分决策，而非一次性求解全部决策；每个时间段的决策结果作为下一个时间段的初始值，通过迭代不断更新决策结果，最终得到全局最优解，再利用遗传算法，求得每个时间段客户订单分配后的最优路径，再由运输车辆进行配送。
48、进一步，步骤s3中，所述贪婪算法是当有客户新订单到来时，配送员需要判断是否服务完下一个客户点后立即返回配送起点取货，并根据回到配送起点的时刻和当前未配送的订单构成的新路径之间的关系，判断是否需要在配送起点等待后再出发，配送步骤如下：
49、s311：配送员位于配送起点时，如果没有新订单出现，则持续在配送起点等待，需求订单一直累计待到时刻t时，订单序列开始出现，此时使用步骤s313计算出一条最优路径τ来配送当前已出现但未被配送的所有订单，并返回配送起点，记路径τ的长度为|τ|；如果当前时刻配送员立刻出发去配送当前已出现的订单序列，且当配送员在配送途中有新订单出现时，立即根据步骤s312判断是否立即沿最短路径返回配送起点取货并等待；如果配送员将在配送起点等待至当前时刻与相等时再出发，且当配送员在配送途中有新订单出现时，立即根据步骤s312判断是否立即沿最短路径返回配送起点取货并等待；
50、s312：假设ti时刻，在x处出现了一个新订单ri＝(ti,x)，x的后继节点为kx；此时配送员正根据步骤s313计算出当前已出现但未被配送的所有订单，并返回配送起点的最优路径τ进行配送，记路径τ的长度为|τ|；配送员当前的位置为y，y的后继订单点为ky；τ'为配送员在ky处返回配送起点后，立即根据步骤s313重新计算出当前已出现但未被配送的所有订单并回到配送起点的最优路径τ'，配送当前已出现但未被配送的所有订单，记路径τ'的长度为|τ'|；
51、(1)如果d(o,ky)+d(ky,o)+|τ'|-|τ|≤d(o,kx)+d(kx,o)，配送员到达当前位置的后继节点后，立刻返回配送起点取货，进入步骤s311；如果配送员返回配送起点途中有新订单释放，则忽略该订单；其中，d(o,ky)表示配送员从起点到节点i的路径，d(ky,o)表示从节点i返回起点的路径；
52、(2)如果d(o,ky)+d(ky,o)+|τ'|-|τ|＞d(o,kx)+d(kx,o)，配送员忽略ri，继续按照路径τ配送，并在配送完本次所有订单后返回配送起点，进入步骤s311；
53、s313：根据贪婪算法形成得一组实时订单序列位置生成初始解，利用遗传算法(ga)解得该初始解的最佳取送货路线，配送员根据路线开始配送此次出发需要配送的订单。
54、进一步，步骤s3中，所述w&i算法(wait and ignore)是基于配送车辆位于配送起点时的某个时刻与已出现订单的后继节点的距离之间的关系来做出行动决策，w&i策略的具体判断方法如下：
55、s321：配送车辆位于配送起点时，如果没有订单出现，则持续在配送起点等待；时刻t，订单序列开始出现，中已出现订单的最长配送距离点为rmax(t,lmax)，rmax(t,lmax)的后继节点kmax与配送起点o之间的距离为lkmax；如果t≥2lkmax，配送车辆立刻出发去配送当前已出现的订单序列且忽略配送途中出现的所有新订单；如果t＜2lkmax，配送车辆将在配送起点等待至当前时刻与2lkmax相等时再出发，且一旦出发，忽略配送途中出现的所有订单；
56、s322：配送车辆出发配送当前所有已出现的订单组成的订单序列时，将根据步骤s324计算一条最优路径前去配送；当配送车辆配送完此时没有新需求出现且配送途中也没有新需求释放，配送车辆在下一个转向路口处立刻返回配送起点等待，直至新订单出现；
57、s323：若订单池没有订单，配送车辆在配送起点等待；
58、s324：根据w&i算法形成得一组实时订单序列位置生成初始解，利用遗传算法(ga)解得该初始解的最佳取送货路线，配送员根据路线开始配送此次出发需要配送的订单。
59、本发明的有益效果在于：本发明可以完善和提升末端配送车辆的效率，在保证配送人员遵守交通规则的前提下，通过合单配送和车辆路径优化来提高的配送效率，其算法将为科学调度大规模实时订单的末端配送车辆路径优化提供理论支持，降低末端配送车辆的总体配送成本。
60、本发明的其他优点、目标和特征在某种程度上将在随后的说明书中进行阐述，并且在某种程度上，基于对下文的考察研究对本领域技术人员而言将是显而易见的，或者可以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书来实现和获得。
1.一种面向大规模客户的末端配送路径优化方法，其特征在于，该方法具体包括以下步骤：
2.根据权利要求1所述的末端配送路径优化方法，其特征在于，步骤s1中，构建面向大规模客户的实时取送货路径优化问题，具体包括以下步骤：
3.根据权利要求2所述的末端配送路径优化方法，其特征在于，步骤s2中，构建的末端客户实时订单路径优化模型的总优化目标函数为：
4.根据权利要求1所述的末端配送路径优化方法，其特征在于，步骤s3中，所述滚动时域算法具体是将问题分成多个时间段，每个时间段只考虑部分决策，而非一次性求解全部决策；每个时间段的决策结果作为下一个时间段的初始值，通过迭代不断更新决策结果，最终得到全局最优解，再利用遗传算法，求得每个时间段客户订单分配后的最优路径，再由运输车辆进行配送。
5.根据权利要求3所述的末端配送路径优化方法，其特征在于，步骤s3中，所述贪婪算法是当有客户新订单到来时，配送员需要判断是否服务完下一个客户点后立即返回配送起点取货，并根据回到配送起点的时刻和当前未配送的订单构成的新路径之间的关系，判断是否需要在配送起点等待后再出发，配送步骤如下：
6.根据权利要求3所述的末端配送路径优化方法，其特征在于，步骤s3中，所述w&i算法是基于配送车辆位于配送起点时的某个时刻与已出现订单的后继节点的距离之间的关系来做出行动决策，w&i策略的具体判断方法如下：
