CN104102953A - 一种物流送货线路优化生成方法及系统 - Google Patents

Abstract

本发明公开了一种物流送货线路优化生成方法及系统，首先获取配送区域内客户信息并聚合形成配送片区；然后按送货车载量选择离物流中心配送工作时间最远的片区为计算源点；按片区内客户线性配送序号或者离源点工作时间最近的下一个送货片区累计客户送货量；直到满足送货车载量，最后完成送货总量并将选择的客户线性配送序号输出作为优化送货线路。本发明采用反向递归的迪杰斯特拉算法来计算合适送货路径，以片区为基本计算单元，简化配送网络，极大降低网络计算量；大大降低了信息采集难度和信息采集时间，减少了送货车的数量和出车次数，降低了运行成本，提升了配送效率。

Description

一种物流送货线路优化生成方法及系统

技术领域

本发明涉及物流配送路径规划领域，特别涉及一种烟草配送过程中的物流送货线路优化生成方法及系统。

背景技术

关于送货模式的探索和线路优化，国内烟草物流多采用“并线减员”方式降低“四定”模式物流成本，随着时间的推移，这种方式已接近极限，有的地市州受各种因素制约，已减无可减；“并线减人”达到一定程度后也与“人本物流”理念相冲突。采用新的送货模式降低物流成本提高运行效率，成为烟草物流研究的新课题。

国内开展了动态送货模式的探索并取得良好的运用效果。根据对这些案例特点提取，国内动态送货模式可分为“动态送货模式”和“弹性送货模式”两大流派，其优缺点如下：动态送货模式的优点是：实现真正意义的实时动态送货；缺点是：技术支撑能力要求高，投入大，只有少数标杆型企业能开发运用，难以在行业现状下推广。弹性送货模式优点是：简单易于理解；缺点是：以人工组合优化为主，对线路编排员能力要求高，物流环境发生变化后，送货线路调整困难，两种模式都存在共同的问题是难于推广。

送货线路优化问题是典型的最短路径问题，但由于卷烟终端配送，具有客户点多面广，销量波动，道路复杂等特点，使最短路径问题模型在解决烟草行业的终端配送实际问题时显得不够灵活。且烟草物流配送基础数据采集量大，传统方法一般采用点对点的计算方式，因而信息采集和建模相对复杂，计算难度较大。同时由于烟草配送网络存在大量的末端支路，导致该算法计算到最后一条配送线路时，剩余的客户基本都处在各末端支路，线路极为迂回。

因此需要一种物流送货线路优化生成方法及系统。

发明内容

有鉴于此，本发明所要解决的技术问题是提供一种物流送货线路优化生成方法及系统。

本发明的目的之一是提出一种物流送货线路优化生成方法；本发明的目的之二是提出一种物流送货线路优化生成系统。

本发明的目的之一是通过以下技术方案来实现的：

本发明提供的一种物流送货线路优化生成方法，包括以下步骤：

S1：获取以物流中心为原点V0的预设配送区域内客户信息；

S2：将客户信息按预设约束条件聚合形成配送片区；

S3：测度各片区到物流中心之间工作时间和相邻片区之间工作时间；

S4：确定同一片区内客户线性配送序号和客户送货量；

S5：获取各片区配送量、送货车载量和送货总量；

S6：按送货车载量选择离物流中心配送工作时间最远的片区作为送货量计算源点v_m；

S7：在源点v_m所在的片区内，按照片区内客户线性配送序号累计客户送货量；

S8：判断客户送货量是否大于送货车载量，如果是，则将选择的客户线性配送序号输出作为优化送货线路，返回步骤S6继续计算离送货量源点v_m工作时间最近的下一个送货片区v_m-1；

S9：如果否，则选择离送货量源点v_m工作时间最近的下一个送货片区v_m-1；按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路；

S10：计算各片区的配送总量；

S11：判断配送总量是否小于送货总量，如果是，则返回步骤S6继续计算以物流中心为原点V0剩余片区的送货线路；

S12：如果否，则结束送货线路的计算。

进一步，所述配送片区包括末端场镇片区、主干道片区、干线场镇片区、城郊片区和市区片区；

所述配送片区是通过以下方式来划分的：

获取以物流中心为原点V0的预设配送区域内的行政区域分布地图；

将分布地图上最末端的场镇及死胡同型的道路支线的客户聚合成末端场镇片区；

将分布地图上各相邻场镇间的主干道的客户聚合成主干道片区；

将分布地图上主干道沿途的沿线场镇的客户聚合成干线场镇片区；

将分布地图上与主干道相邻的城郊的客户聚合成城郊片区；

将分布地图上城区的客户进行分块并聚合成市区片区；

所述各片区包括可分割片区和不可分割片区。

进一步，所述片区内客户序号是根据路网结构、城市街道布局以及道路交通状况，结合送货历史经验，将各片区内的客户按照从近到远，依次排序，形成送货序号。

进一步，所述配送的工作时间是根据以下公式来确定的：

$\begin{array}{ccc}T=t0+K1*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& \mathrm{Si}/\mathrm{Vi}+K2*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& f\left(\mathrm{Mi}\right);\end{array}$

其中，准备时间t0＝晨会时间+(早餐时间)+送货员裁单时间+领货、清点、装车时间+途中+正常休息时间+存款时间+单据交接时间；

其中n为线路的片区数，Si为第(i-1)个片区到i个片区的行驶里程，Vi为第(i-1)个片区到i个片区的行驶速度，行驶速度根据农网与城网不同进行量化；

其中n为线路中的片区数，f(Mi)为i个片区的服务时间，是与该片区的客户数、需求数、服务时间相关的函数关系，通过以下公式计算：

f(Mi)＝m*A+(Mi-m*25)/C+S/V；

其中：m是该片区的客户数；A是每个客户的标准作业时间；Mi是该片区总的卷烟数；C是超出基准条数的服务时间；S该片区总里程；V该片区平均速度，采用统计方法得出；

车辆行进系数K1用于表示员工对线路熟悉度、直接服务顾客系数K2用于表示员工对客户熟悉度。

进一步，所述步骤S9中在按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量之前还包括以下步骤：

S91：判断下一个送货片区v_m-1是否属于可分割片区，如果是，则按照片区内客户线性配送序号继续累计下一个送货片区v_m-1；如果否，则选择离下一个送货片区v_m-1工作时间最近的另外下一个送货片区v_m-2；按照片区内客户线性配送序号继续累计另外下一个送货片区v_m-2的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路。

本发明的目的之二是通过以下技术方案来实现的：

本发明提供的一种物流送货线路优化生成系统，包括配送区域内客户信息采集单元、配送片区聚合单元、片区工作时间计算单元、片区内客户信息单元、片区信息单元、片区源点单元、送货量计算单元、优化线路生成单元、片区配送总量单元、优化线路输出单元；

所述配送区域内客户信息采集单元，用于获取以物流中心为原点V0的预设配送区域内客户信息；

所述配送片区聚合单元，用于将客户信息按预设约束条件聚合形成配送片区；

所述片区工作时间计算单元，用于测度各片区到物流中心之间工作时间和相邻片区之间工作时间；

所述片区内客户信息单元，用于确定同一片区内客户线性配送序号和客户送货量；

所述片区信息单元，用于获取各片区配送量、送货车载量和送货总量；

所述片区源点单元，用于按送货车载量选择离物流中心配送工作时间最远的片区作为送货量计算源点v_m；

所述送货量计算单元，用于在源点v_m所在的片区内，按照片区内客户线性配送序号累计客户送货量；

所述优化线路生成单元，用于判断客户送货量是否大于送货车载量，如果是，则将选择的客户线性配送序号输出作为优化送货线路，返回步骤S6继续计算离送货量源点v_m工作时间最近的下一个送货片区v_m-1；如果否，则选择离送货量源点v_m工作时间最近的下一个送货片区v_m-1；按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路；

所述片区配送总量单元，用于计算各片区的配送总量；并判断配送总量是否小于送货总量，如果是，则返回步骤S6继续计算以物流中心为原点V0剩余片区的送货线路；如果否，则结束送货线路的计算；

所述优化线路输出单元，用于输出优化送货线路。

进一步，所述配送片区包括末端场镇片区、主干道片区、干线场镇片区、城郊片区和市区片区；

所述配送片区是通过以下方式来划分的：

获取以物流中心为原点V0的预设配送区域内的行政区域分布地图；

将分布地图上最末端的场镇及死胡同型的道路支线的客户聚合成末端场镇片区；

将分布地图上各相邻场镇间的主干道的客户聚合成主干道片区；

将分布地图上主干道沿途的沿线场镇的客户聚合成干线场镇片区；

将分布地图上与主干道相邻的城郊的客户聚合成城郊片区；

将分布地图上城区的客户进行分块并聚合成市区片区；

所述各片区包括可分割片区和不可分割片区。

进一步，所述片区内客户序号是根据路网结构、城市街道布局以及道路交通状况，结合送货历史经验，将各片区内的客户按照从近到远，依次排序，形成送货序号。

进一步，所述片区工作时间计算单元中的工作时间是根据以下公式来确定的：

$\begin{array}{ccc}T=t0+K1*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& \mathrm{Si}/\mathrm{Vi}+K2*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& f\left(\mathrm{Mi}\right);\end{array}$

其中，准备时间t0＝晨会时间+(早餐时间)+送货员裁单时间+领货、清点、装车时间+途中+正常休息时间+存款时间+单据交接时间；

其中n为线路的片区数，Si为第(i-1)个片区到i个片区的行驶里程，Vi为第(i-1)个片区到i个片区的行驶速度，行驶速度根据农网与城网不同进行量化；

其中n为线路中的片区数，f(Mi)为i个片区的服务时间，是与该片区的客户数、需求数、服务时间相关的函数关系，通过以下公式计算：

f(Mi)＝m*A+(Mi-m*25)/C+S/V；

其中：m是该片区的客户数；A是每个客户的标准作业时间；Mi是该片区总的卷烟数；C是超出基准条数的服务时间；S该片区总里程；V该片区平均速度，采用统计方法得出；

车辆行进系数K1用于表示员工对线路熟悉度、直接服务顾客系数K2用于表示员工对客户熟悉度。

进一步，所述所述优化线路生成单元中在按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量之前还包括以下步骤：

S91：判断下一个送货片区v_m-1是否属于可分割片区，如果是，则按照片区内客户线性配送序号继续累计下一个送货片区v_m-1；如果否，则选择离下一个送货片区v_m-1工作时间最近的另外下一个送货片区v_m-2；按照片区内客户线性配送序号继续累计另外下一个送货片区v_m-2的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路。

本发明的有益效果在于：本发明采用反向递归的迪杰斯特拉算法来解决网络中从某个特定点到其他顶点的合适路径计算算法。采用片区划分和片区内客户的线性关系，以片区为基本计算分配单元，简化配送网络，可极大降低网络计算量；同时按照反向递归的原则，把迪杰斯特拉算法中的最短目标变成了最远目标。通过以上变化，改善后的迪杰斯特拉算法，更加适用于本项目实际应用。克服了传统的迪杰斯特拉算法中以每一位客户点为计算单元的大数据采集和计算的问题，大大降低了信息采集难度和信息采集时间，采用片区的方式，则只需采集片区内某些客户的地理信息作为计算源点，且不需要十分精确，gps数据偏移不严重即可，能减少送货车的数量和出车次数，降低了运行成本，降低了劳动强度，提升了配送效率。

附图说明

为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步的详细描述，其中：

图1为本发明实施例提供的物流送货线路优化生成方法实施例1流程图；

图2为本发明实施例提供的物流送货线路优化生成系统图；

图3为本发明实施例提供的物流送货线路优化生成方法实施例2流程图；

图4为本发明实施例提供的物流送货线路优化生成方法实施例3工作过程图。

具体实施方式

以下将参照附图，对本发明的优选实施例进行详细的描述。应当理解，优选实施例仅为了说明本发明，而不是为了限制本发明的保护范围。

实施例1

图1为本发明实施例提供的物流送货线路优化生成方法实施例1流程图，如图所示：本发明提供的一种物流送货线路优化生成方法，包括以下步骤：

S1：获取以物流中心为原点V0的预设配送区域内客户信息；

S2：将客户信息按预设约束条件聚合形成配送片区；

S3：测度各片区到物流中心之间工作时间和相邻片区之间工作时间；

S4：确定同一片区内客户线性配送序号和客户送货量；

S5：获取各片区配送量、送货车载量和送货总量；

S6：按送货车载量选择离物流中心配送工作时间最远的片区作为送货量计算源点v_m；

S7：在源点v_m所在的片区内，按照片区内客户线性配送序号累计客户送货量；

S8：判断客户送货量是否大于送货车载量，如果是，则将选择的客户线性配送序号输出作为优化送货线路，返回步骤S6继续计算离送货量源点v_m工作时间最近的下一个送货片区v_m-1；

S9：如果否，则选择离送货量源点v_m工作时间最近的下一个送货片区v_m-1；按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路；

S10：计算各片区的配送总量；

S11：判断配送总量是否小于送货总量，如果是，则返回步骤S6继续计算以物流中心为原点V0剩余片区的送货线路；

S12：如果否，则结束送货线路的计算。

所述配送片区包括末端场镇片区、主干道片区、干线场镇片区、城郊片区和市区片区；

所述配送片区是通过以下方式来划分的：

获取以物流中心为原点V0的预设配送区域内的行政区域分布地图；

将分布地图上最末端的场镇及死胡同型的道路支线的客户聚合成末端场镇片区；

将分布地图上各相邻场镇间的主干道的客户聚合成主干道片区；

将分布地图上主干道沿途的沿线场镇的客户聚合成干线场镇片区；

将分布地图上与主干道相邻的城郊的客户聚合成城郊片区；

将分布地图上城区的客户进行分块并聚合成市区片区；

所述各片区包括可分割片区和不可分割片区。

所述片区内客户序号是根据路网结构、城市街道布局以及道路交通状况，结合送货历史经验，将各片区内的客户按照从近到远，依次排序，形成送货序号。

所述配送的工作时间T是根据以下公式来确定的：

$\begin{array}{ccc}T=t0+K1*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& \mathrm{Si}/\mathrm{Vi}+K2*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& f\left(\mathrm{Mi}\right);\end{array}$

其中，准备时间t0＝晨会时间+(早餐时间)+送货员裁单时间+领货、清点、装车时间+途中+正常休息时间+存款时间+单据交接时间；

其中n为线路的片区数，Si为第(i-1)个片区到i个片区的行驶里程，Vi为第(i-1)个片区到i个片区的行驶速度，行驶速度根据农网与城网不同进行量化；

其中n为线路中的片区数，f(Mi)为i个片区的服务时间，是与该片区的客户数、需求数、服务时间相关的函数关系，通过以下公式计算：

f(Mi)＝m*A+(Mi-m*25)/C+S/V；

其中：m是该片区的客户数；A是每个客户的标准作业时间；Mi是该片区总的卷烟数；C是超出基准条数的服务时间；S该片区总里程；V该片区平均速度，采用统计方法得出；

车辆行进系数K1用于表示员工对线路熟悉度、直接服务顾客系数K2用于表示员工对客户熟悉度。

所述步骤S9中在按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量之前还包括以下步骤：

S91：判断下一个送货片区v_m-1是否属于可分割片区，如果是，则按照片区内客户线性配送序号继续累计下一个送货片区v_m-1；如果否，则选择离下一个送货片区v_m-1工作时间最近的另外下一个送货片区v_m-2；按照片区内客户线性配送序号继续累计另外下一个送货片区v_m-2的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路。

图2为本发明实施例提供的物流送货线路优化生成系统图；本实施例还提供了一种物流送货线路优化生成系统，包括配送区域内客户信息采集单元、配送片区聚合单元、片区工作时间计算单元、片区内客户信息单元、片区信息单元、片区源点单元、送货量计算单元、优化线路生成单元、片区配送总量单元、优化线路输出单元；

所述配送区域内客户信息采集单元，用于获取以物流中心为原点V0的预设配送区域内客户信息；

所述配送片区聚合单元，用于将客户信息按预设约束条件聚合形成配送片区；

所述片区工作时间计算单元，用于测度各片区到物流中心之间工作时间和相邻片区之间工作时间；

所述片区内客户信息单元，用于确定同一片区内客户线性配送序号和客户送货量；

所述片区信息单元，用于获取各片区配送量、送货车载量和送货总量；

所述片区源点单元，用于按送货车载量选择离物流中心配送工作时间最远的片区作为送货量计算源点v_m；

所述送货量计算单元，用于在源点v_m所在的片区内，按照片区内客户线性配送序号累计客户送货量；

所述优化线路生成单元，用于判断客户送货量是否大于送货车载量，如果是，则将选择的客户线性配送序号输出作为优化送货线路，返回步骤S6继续计算离送货量源点v_m工作时间最近的下一个送货片区v_m-1；如果否，则选择离送货量源点v_m工作时间最近的下一个送货片区v_m-1；按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路；

所述片区配送总量单元，用于计算各片区的配送总量；并判断配送总量是否小于送货总量，如果是，则返回步骤S6继续计算以物流中心为原点V0剩余片区的送货线路；如果否，则结束送货线路的计算；

所述优化线路输出单元，用于输出优化送货线路。

所述配送片区包括末端场镇片区、主干道片区、干线场镇片区、城郊片区和市区片区；

所述配送片区是通过以下方式来划分的：

获取以物流中心为原点V0的预设配送区域内的行政区域分布地图；

将分布地图上最末端的场镇及死胡同型的道路支线的客户聚合成末端场镇片区；

将分布地图上各相邻场镇间的主干道的客户聚合成主干道片区；

将分布地图上主干道沿途的沿线场镇的客户聚合成干线场镇片区；

将分布地图上与主干道相邻的城郊的客户聚合成城郊片区；

将分布地图上城区的客户进行分块并聚合成市区片区；

所述各片区包括可分割片区和不可分割片区。

所述片区内客户序号是根据路网结构、城市街道布局以及道路交通状况，结合送货历史经验，将各片区内的客户按照从近到远，依次排序，形成送货序号。

所述片区工作时间计算单元中的工作时间是根据以下公式来确定的：

$\begin{array}{ccc}T=t0+K1*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& \mathrm{Si}/\mathrm{Vi}+K2*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& f\left(\mathrm{Mi}\right);\end{array}$

其中，准备时间t0＝晨会时间+(早餐时间)+送货员裁单时间+领货、清点、装车时间+途中+正常休息时间+存款时间+单据交接时间；

其中n为线路的片区数，Si为第(i-1)个片区到i个片区的行驶里程，Vi为第(i-1)个片区到i个片区的行驶速度，行驶速度根据农网与城网不同进行量化；

其中n为线路中的片区数，f(Mi)为i个片区的服务时间，是与该片区的客户数、需求数、服务时间相关的函数关系，通过以下公式计算：

f(Mi)＝m*A+(Mi-m*25)/C+S/V；

其中：m是该片区的客户数；A是每个客户的标准作业时间；Mi是该片区总的卷烟数；C是超出基准条数的服务时间；S该片区总里程；V该片区平均速度，采用统计方法得出；

车辆行进系数K1用于表示员工对线路熟悉度、直接服务顾客系数K2用于表示员工对客户熟悉度。

所述所述优化线路生成单元中在按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量之前还包括以下步骤：

S91：判断下一个送货片区v_m-1是否属于可分割片区，如果是，则按照片区内客户线性配送序号继续累计下一个送货片区v_m-1；如果否，则选择离下一个送货片区v_m-1工作时间最近的另外下一个送货片区v_m-2；按照片区内客户线性配送序号继续累计另外下一个送货片区v_m-2的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路。

实施例2

图3为本发明实施例提供的物流送货线路优化生成方法实施例2流程图，如图所示，本实施例与实施例1的区别仅在于：

S21：获取配送区域内客户配送点信息；

S22：将客户配送点信息按预设约束条件聚合形成配送片区；

S23：测度各片区到物流中心和片区之间距离；

S24：获取各片区和区内客户未满足订单量；

S25：判断各片区是否已在优化线路表之中且各片区配送量是否完成；

S26：如果是，则进行步骤S；如果否，则遍历各片区，判断其需求配送量是否小于大型车运载量；

S27：如果否，则判断是否选择直接派大型车送到该片区；如果是，则按区内客户按线性关系顺序配送；记录区内未满足需求客户信息并更新配送订单；更新线路表和派车情况表；如果否，则返回步骤S24；

S28：如果是，则生成各片区组成的配送线路表和派车表，并注明线路中距物流中心最远端片区，以备优先配送；

S29：判断线路所用车型是否有剩余载荷且最邻近片区内是否有片区存在未满足配送订单，客户且未满足量是否小于或等于车载剩余量；

如果否，则返回步骤S4；如果是，则将两个片区相连，更新路线表，更新该路线运载量，更新客户信息和配送订单，并返回步骤S24；

S210：在每条路线中最后加上物流中心点构成回路；

S211：根据每条线路的运载量来搭配车型；

S212：输出结果，包括路线、车型、路程；

S213：结束；

实施例3

图4为本发明实施例提供的物流送货线路优化生成方法实施例3工作过程图，如图所示，本实施例与实施例1的区别仅在于：

图中，A为配送中心，即计算源点；图中各点构成了配送过程中需要到达的片区；点与点之间的值，通过时间来确定，也可以理解为在点与点之间的路径长短基础上，加上各点自身的时间约束条件(如：停车时间、卸货时间等等)，然后转换为工作时间条件。

下面举例具体说明本实施例提供的物流送货线路优化生成方法的工作过程：

a)设物流中心为原点V0，W为当天要送货的客户片区Vm(m从1到203)的集合，Si为已经安排了的客户集合(线路)，其中为当天送货总量；

b)W中的点Vm对应的权重值规定如下:为V0到Vm的时间参数与Vm自身的时间参数之和；

c)然后从W中的点中选一个满足其距离值与VO为最远的点Vm加入到Si中；(反向递归由远及近原则)；

d)然后在Vm片区内，按照该片区建立的片区内客户线性序号，根据序号的由小到大，自动寻找下一个客户Vmk；(应用片区内的客户线性关系)；

e)如果在Vm片区内,通过d)步骤满足了则完成了Si线路的重组，回到c)，进行d)和e)步骤；

f)如果在Vm片区内,通过d)步骤不能实现则按照与Vm片区最近的原则选择下一个片区Vk；

g)在Vk片区内，按照该片区建立的片区内客户线性序号，根据序号的由小到大，自动寻找下一个客户Vkk,直到满足完成Si线路的重组；

h)如此迭代循环进行下去,直到Si满足了一条线路的要求；

e)然后再次以物流中心为原点V0进行下一条线路Si的计算。过程按上述步骤进行。直到完成了当天的送货量为止。

举例：某天配送计划如下：客户数10户分布在3个片区，总送货量为100件，假设安排的送货车载货量为20件，具体如下：

线路组合过程如下：

按照与物流中心距离最远的原则，选定了片区1-1；

在片区1-1内按客户的线性关系依次选定了客户1和客户2，满足了送货车的载货量要求，完成了第一条线路的安排；

再次按照与物流中心距离最远的原则，再次选定了片区1-1；

在片区1-1内按客户的线性关系选定了客户3，此时片区1-1内客户已经安排完，但送货车的载货量还有10件的缺口；

以片区1-1为原点计算与其最近距离的片区，选定了片区1-2；

在片区1-2内按客户的线性关系依次选定了客户1，满足了送货车的载货量20件要求，完成了第二条线路的安排；

重复上述过程，直到完成了当天送货量100件的任务。

最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管通过参照本发明的优选实施例已经对本发明进行了描述，但本领域的普通技术人员应当理解，可以在形式上和细节上对其作出各种各样的改变，而不偏离本发明所限定的精神和范围。

Claims (10)

1.一种物流送货线路优化生成方法，其特征在于：包括以下步骤：

S1：获取以物流中心为原点V0的预设配送区域内客户信息；

S2：将客户信息按预设约束条件聚合形成配送片区；

S3：测度各片区到物流中心之间工作时间和相邻片区之间工作时间；

S4：确定同一片区内客户线性配送序号和客户送货量；

S5：获取各片区配送量、送货车载量和送货总量；

S6：按送货车载量选择离物流中心配送工作时间最远的片区作为送货量计算源点v_m；

S7：在源点v_m所在的片区内，按照片区内客户线性配送序号累计客户送货量；

S8：判断客户送货量是否大于送货车载量，如果是，则将选择的客户线性配送序号输出作为优化送货线路，返回步骤S6继续计算离送货量源点v_m工作时间最近的下一个送货片区v_m-1；

S9：如果否，则选择离送货量源点v_m工作时间最近的下一个送货片区v_m-1；按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路；

S10：计算各片区的配送总量；

S11：判断配送总量是否小于送货总量，如果是，则返回步骤S6继续计算以物流中心为原点V0剩余片区的送货线路；

S12：如果否，则结束送货线路的计算。

2.根据权利要求1所述的，其特征在于：所述配送片区包括末端场镇片区、主干道片区、干线场镇片区、城郊片区和市区片区；

所述配送片区是通过以下方式来划分的：

获取以物流中心为原点V0的预设配送区域内的行政区域分布地图；

将分布地图上最末端的场镇及死胡同型的道路支线的客户聚合成末端场镇片区；

将分布地图上各相邻场镇间的主干道的客户聚合成主干道片区；

将分布地图上主干道沿途的沿线场镇的客户聚合成干线场镇片区；

将分布地图上与主干道相邻的城郊的客户聚合成城郊片区；

将分布地图上城区的客户进行分块并聚合成市区片区；

所述各片区包括可分割片区和不可分割片区。

3.根据权利要求1所述的，其特征在于：所述片区内客户序号是根据路网结构、城市街道布局以及道路交通状况，结合送货历史经验，将各片区内的客户按照从近到远，依次排序，形成送货序号。

4.根据权利要求1所述的，其特征在于：所述配送的工作时间是根据以下公式来确定的：

$\begin{array}{ccc}T=t0+K1*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& \mathrm{Si}/\mathrm{Vi}+K2*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& f\left(\mathrm{Mi}\right);\end{array}$

其中，准备时间t0＝晨会时间+(早餐时间)+送货员裁单时间+领货、清点、装车时间+途中+正常休息时间+存款时间+单据交接时间；

其中n为线路的片区数，Si为第(i-1)个片区到i个片区的行驶里程，Vi为第(i-1)个片区到i个片区的行驶速度，行驶速度根据农网与城网不同进行量化；

其中n为线路中的片区数，f(Mi)为i个片区的服务时间，是与该片区的客户数、需求数、服务时间相关的函数关系，通过以下公式计算：

f(Mi)＝m*A+(Mi-m*25)/C+S/V；

其中：m是该片区的客户数；A是每个客户的标准作业时间；Mi是该片区总的卷烟数；C是超出基准条数的服务时间；S该片区总里程；V该片区平均速度，采用统计方法得出；

车辆行进系数K1用于表示员工对线路熟悉度、直接服务顾客系数K2用于表示员工对客户熟悉度。

5.根据权利要求1所述的，其特征在于：所述步骤S9中在按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量之前还包括以下步骤：

S91：判断下一个送货片区v_m-1是否属于可分割片区，如果是，则按照片区内客户线性配送序号继续累计下一个送货片区v_m-1；如果否，则选择离下一个送货片区v_m-1工作时间最近的另外下一个送货片区v_m-2；按照片区内客户线性配送序号继续累计另外下一个送货片区v_m-2的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路。

6.一种物流送货线路优化生成系统，其特征在于：包括配送区域内客户信息采集单元、配送片区聚合单元、片区工作时间计算单元、片区内客户信息单元、片区信息单元、片区源点单元、送货量计算单元、优化线路生成单元、片区配送总量单元、优化线路输出单元；

所述配送区域内客户信息采集单元，用于获取以物流中心为原点V0的预设配送区域内客户信息；

所述配送片区聚合单元，用于将客户信息按预设约束条件聚合形成配送片区；

所述片区工作时间计算单元，用于测度各片区到物流中心之间工作时间和相邻片区之间工作时间；

所述片区内客户信息单元，用于确定同一片区内客户线性配送序号和客户送货量；

所述片区信息单元，用于获取各片区配送量、送货车载量和送货总量；

所述片区源点单元，用于按送货车载量选择离物流中心配送工作时间最远的片区作为送货量计算源点v_m；

所述送货量计算单元，用于在源点v_m所在的片区内，按照片区内客户线性配送序号累计客户送货量；

所述优化线路生成单元，用于判断客户送货量是否大于送货车载量，如果是，则将选择的客户线性配送序号输出作为优化送货线路，返回步骤S6继续计算离送货量源点v_m工作时间最近的下一个送货片区v_m-1；如果否，则选择离送货量源点v_m工作时间最近的下一个送货片区v_m-1；按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路；

所述片区配送总量单元，用于计算各片区的配送总量；并判断配送总量是否小于送货总量，如果是，则返回步骤S6继续计算以物流中心为原点V0剩余片区的送货线路；如果否，则结束送货线路的计算；

所述优化线路输出单元，用于输出优化送货线路。

7.根据权利要求1所述的，其特征在于：所述配送片区包括末端场镇片区、主干道片区、干线场镇片区、城郊片区和市区片区；

所述配送片区是通过以下方式来划分的：

获取以物流中心为原点V0的预设配送区域内的行政区域分布地图；

将分布地图上最末端的场镇及死胡同型的道路支线的客户聚合成末端场镇片区；

将分布地图上各相邻场镇间的主干道的客户聚合成主干道片区；

将分布地图上主干道沿途的沿线场镇的客户聚合成干线场镇片区；

将分布地图上与主干道相邻的城郊的客户聚合成城郊片区；

将分布地图上城区的客户进行分块并聚合成市区片区；

所述各片区包括可分割片区和不可分割片区。

8.根据权利要求1所述的，其特征在于：所述片区内客户序号是根据路网结构、城市街道布局以及道路交通状况，结合送货历史经验，将各片区内的客户按照从近到远，依次排序，形成送货序号。

9.根据权利要求1所述的，其特征在于：所述片区工作时间计算单元中的工作时间是根据以下公式来确定的：

$\begin{array}{ccc}T=t0+K1*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& \mathrm{Si}/\mathrm{Vi}+K2*\underset{i=1}{\overset{n}{\mathrm{\Σ}}}& f\left(\mathrm{Mi}\right);\end{array}$

其中，准备时间t0＝晨会时间+(早餐时间)+送货员裁单时间+领货、清点、装车时间+途中+正常休息时间+存款时间+单据交接时间；

其中n为线路的片区数，Si为第(i-1)个片区到i个片区的行驶里程，Vi为第(i-1)个片区到i个片区的行驶速度，行驶速度根据农网与城网不同进行量化；

其中n为线路中的片区数，f(Mi)为i个片区的服务时间，是与该片区的客户数、需求数、服务时间相关的函数关系，通过以下公式计算：

f(Mi)＝m*A+(Mi-m*25)/C+S/V；

其中：m是该片区的客户数；A是每个客户的标准作业时间；Mi是该片区总的卷烟数；C是超出基准条数的服务时间；S该片区总里程；V该片区平均速度，采用统计方法得出；

车辆行进系数K1用于表示员工对线路熟悉度、直接服务顾客系数K2用于表示员工对客户熟悉度。

10.根据权利要求1所述的，其特征在于：所述所述优化线路生成单元中在按照片区内客户线性配送序号继续累计下一个送货片区v_m-1的客户送货量之前还包括以下步骤：

S91：判断下一个送货片区v_m-1是否属于可分割片区，如果是，则按照片区内客户线性配送序号继续累计下一个送货片区v_m-1；如果否，则选择离下一个送货片区v_m-1工作时间最近的另外下一个送货片区v_m-2；按照片区内客户线性配送序号继续累计另外下一个送货片区v_m-2的客户送货量，直到满足送货车载量，并将选择的客户线性配送序号输出作为优化送货线路。