论文部分内容阅读
摘 要：B2C和O2O两种电子商务模式的发展，带动了物流配送的高速发展。然而目前的B2C和O2O订单独立配送模式下存在资源利用不充分、配送成本高的问题，本文提出B2C和O2O的联合配送模式，并设计优化算法根据实际数据为快递员规划最优配送路径。
关键词：联合配送 路径规划
一、引言
目前国内的电商物流占物流业务比重超过60%。在整个物流配送过程中距离最短的最后一公里配送环节却占了物流配送时间的20%，对配送环节的优化能大幅提升物流配送效率。
最后一公里配送环节优化主要问题在于配送路径规划（VRP）。VRP问题由Dantzig于1959年首次提出，Clarke和Wright将VRP问题转变成线性最优化问题并应用到物流和交通领域，Lenstra证明VRP问题是NP-hard问题，小规模情况下可采用精确算法求解，但是对于大规模问题只能采用启发式算法或智能优化算法求解。
随着O2O电商模式的日益发展，互联网逐渐向线下渗透，据艾瑞咨询数据显示，2016年中国本地生活O2O行业市场规模达7620.6亿元，较2015年增长71.8%；线上餐饮类业务占行业市场规模54.9%。然而由于O2O订单的时间聚集性，且B2C订单和O2O订单目前采用独立配送模式，导致以下两个问题：（1）在O2O快件配送需求较低的时期，O2O快递员处于空闲状态；（2）B2C快件和O2O快件配送地址存在较高的重合度，B2C快递员的配送能力未被充分利用。采用B2C和O2O订单联合配送方式能提高资源利用率，大幅降低总体配送成本。
二、问题描述
在一定区域内分布有N个配送中心，覆盖全区域的B2C订单配送，每天早上8：00当天所有待配送的B2C订单到达配送中心，8：00开始快递员从配送中心出发开始配送订单，至晚上20：00前完成所有B2C订单的配送，每一名快递员可进入任何配送中心取件，取件和派件时间分别与取件和派件量有关。除B2C订单外，快递员还要负责O2O订单的配送。O2O订单有两个时间限制：一是不得早于指定取件时间到达，否则需等待至指定取件时间方能取件；二是不得晚于指定最晚派件时间，否则要加上一定的惩罚，若早于指定配送时间到达可直接完成配送无需等待。每名快递员携带的快件数量是有限的。
快递员的配送路径有如下几个特点：（1）快递员可能多次返回配送中心取件；（2）快递员可能多次访问同一家线下商店取件；（3）快递员可能多次为同一为客户派件。配送路径保证每个节点必须被访问且只能被访问依次，类似于TSP问题，但是与TSP问题不同的是：（1）每个节点的访问都有时间窗，B2C快件可认为是8：00-20：00，O2O快件的取件时间窗可认为是最早取件时间到当天20：00，O2O快件的派件时间窗是最早取件时间到最晚派件时间；（2）访问派件节点之前必须先访问对应的取件节点，否则会导致到了派件节点处无件可派；（3）取件节点和派件节点成对存在，即有对应的取件节点必定有对应的派件节点。
三、算法设计
PDPTW（Pickup and Delivery Problem with Time Windows）属于NP-Hard问题，本文设计遗传算法进行求解。具体计算过程如下：
（1）编码。每一条染色体采用自然数编码，1到N（快递员数量）表示N为配送员的编号，N+1到N+M（订单数量）表示取件点，N+M+1到N+2M表示派件点，从快递员编号开始到下一个快递员编号前为止表示该快递员所负责配送的订单取派件节点。
（2）初始化。随机生成1到N+2M的序列。
（3）有效性检验。出现在快递员配送路径上的取件节点，其对应的派件节点必须出现在该快递员配送路径上且在在取件节点之后。
（4）适应度。依次计算每一位快递员的配送成本，从0开始计算时间，若配送时间晚于时间窗则加上适当惩罚，总配送时间为配送完最后一单时间与惩罚时间之和，由于目标是找到配送耗时最短的路径，因此耗时越短适应度越高，可将所有染色体对应配送总耗时采用正态规范化后取倒数得到适应度。
（5）选择。轮盘赌法，即计算每个染色体的适应度占适应度总和的比值，作为染色体遗传到下一代的概率。
（6）交叉。随机选择两条染色体，并且随机选择一定长度的片段互相交换，交换后由于可能存在使得两条染色体均无效，所以需要再进行校验。
（7）变异。在同一条染色体上随机选择两个位置互相交换，并对交换后的染色体进行校验。
四、算例分析
考虑一个配送中心，有一位快递员，需要完成8个B2C订单和3和O2O订单的配送，订单编号、配送点、取件点、订单包含包裹数和时间窗如表4-1所示，根据以上算法得到最优路径如表4-2所示，路徑总时间成本为636分钟，订单均在时间窗内完成配送。
五、结语
本文基于B2C电商和O2O电商发展规模和趋势，分析了目前B2C订单和O2O订单独立配送模式所存在的两点不足之处：（1）在O2O快件配送需求较低的时期，O2O快递员处于空闲状态；（2）B2C快件和O2O快件配送地址存在较高的重合度，B2C快递员的配送能力未被充分利用。然后据此提出B2C和O2O订单联合配送模式，并设计联合配送模式下配送员最优路径规划算法，最后设计算例并应用所设计的算法得到最有快递员配送路径，结果表明算法在可接受的时间内能够得到最优配送路径，且在独立配送模式下需由两位配送员才能完成的配送任务在联合配送模式下仅由一名配送员即能在所要求时间窗内完成。
参考文献：
[1]Dantzig G B， Ramser J H.The truck dispatching problem[J]. Management science， 1959， 6（1）： 80-91.
[2]Clarke G， Wright J W. Scheduling of vehicles from a central depot to a number of delivery points[J].Operations research， 1964， 12（4）： 568-581.
[3]Lenstra J K， Kan A H G. Complexity of vehicle routing and scheduling problems[J].Networks， 1981， 11（2）： 221-227.
[4]Lin S. Computer solutions of the traveling salesman problem[J]. The Bell system technical journal， 1965， 44（10）： 2245-2269.
[5]Glover F.Future paths for integer programming and links to artificial intelligence[J].Computers & operations research， 1986， 13（5）： 533-549.
关键词：联合配送 路径规划
一、引言
目前国内的电商物流占物流业务比重超过60%。在整个物流配送过程中距离最短的最后一公里配送环节却占了物流配送时间的20%，对配送环节的优化能大幅提升物流配送效率。
最后一公里配送环节优化主要问题在于配送路径规划（VRP）。VRP问题由Dantzig于1959年首次提出，Clarke和Wright将VRP问题转变成线性最优化问题并应用到物流和交通领域，Lenstra证明VRP问题是NP-hard问题，小规模情况下可采用精确算法求解，但是对于大规模问题只能采用启发式算法或智能优化算法求解。
随着O2O电商模式的日益发展，互联网逐渐向线下渗透，据艾瑞咨询数据显示，2016年中国本地生活O2O行业市场规模达7620.6亿元，较2015年增长71.8%；线上餐饮类业务占行业市场规模54.9%。然而由于O2O订单的时间聚集性，且B2C订单和O2O订单目前采用独立配送模式，导致以下两个问题：（1）在O2O快件配送需求较低的时期，O2O快递员处于空闲状态；（2）B2C快件和O2O快件配送地址存在较高的重合度，B2C快递员的配送能力未被充分利用。采用B2C和O2O订单联合配送方式能提高资源利用率，大幅降低总体配送成本。
二、问题描述
在一定区域内分布有N个配送中心，覆盖全区域的B2C订单配送，每天早上8：00当天所有待配送的B2C订单到达配送中心，8：00开始快递员从配送中心出发开始配送订单，至晚上20：00前完成所有B2C订单的配送，每一名快递员可进入任何配送中心取件，取件和派件时间分别与取件和派件量有关。除B2C订单外，快递员还要负责O2O订单的配送。O2O订单有两个时间限制：一是不得早于指定取件时间到达，否则需等待至指定取件时间方能取件；二是不得晚于指定最晚派件时间，否则要加上一定的惩罚，若早于指定配送时间到达可直接完成配送无需等待。每名快递员携带的快件数量是有限的。
快递员的配送路径有如下几个特点：（1）快递员可能多次返回配送中心取件；（2）快递员可能多次访问同一家线下商店取件；（3）快递员可能多次为同一为客户派件。配送路径保证每个节点必须被访问且只能被访问依次，类似于TSP问题，但是与TSP问题不同的是：（1）每个节点的访问都有时间窗，B2C快件可认为是8：00-20：00，O2O快件的取件时间窗可认为是最早取件时间到当天20：00，O2O快件的派件时间窗是最早取件时间到最晚派件时间；（2）访问派件节点之前必须先访问对应的取件节点，否则会导致到了派件节点处无件可派；（3）取件节点和派件节点成对存在，即有对应的取件节点必定有对应的派件节点。
三、算法设计
PDPTW（Pickup and Delivery Problem with Time Windows）属于NP-Hard问题，本文设计遗传算法进行求解。具体计算过程如下：
（1）编码。每一条染色体采用自然数编码，1到N（快递员数量）表示N为配送员的编号，N+1到N+M（订单数量）表示取件点，N+M+1到N+2M表示派件点，从快递员编号开始到下一个快递员编号前为止表示该快递员所负责配送的订单取派件节点。
（2）初始化。随机生成1到N+2M的序列。
（3）有效性检验。出现在快递员配送路径上的取件节点，其对应的派件节点必须出现在该快递员配送路径上且在在取件节点之后。
（4）适应度。依次计算每一位快递员的配送成本，从0开始计算时间，若配送时间晚于时间窗则加上适当惩罚，总配送时间为配送完最后一单时间与惩罚时间之和，由于目标是找到配送耗时最短的路径，因此耗时越短适应度越高，可将所有染色体对应配送总耗时采用正态规范化后取倒数得到适应度。
（5）选择。轮盘赌法，即计算每个染色体的适应度占适应度总和的比值，作为染色体遗传到下一代的概率。
（6）交叉。随机选择两条染色体，并且随机选择一定长度的片段互相交换，交换后由于可能存在使得两条染色体均无效，所以需要再进行校验。
（7）变异。在同一条染色体上随机选择两个位置互相交换，并对交换后的染色体进行校验。
四、算例分析
考虑一个配送中心，有一位快递员，需要完成8个B2C订单和3和O2O订单的配送，订单编号、配送点、取件点、订单包含包裹数和时间窗如表4-1所示，根据以上算法得到最优路径如表4-2所示，路徑总时间成本为636分钟，订单均在时间窗内完成配送。
五、结语
本文基于B2C电商和O2O电商发展规模和趋势，分析了目前B2C订单和O2O订单独立配送模式所存在的两点不足之处：（1）在O2O快件配送需求较低的时期，O2O快递员处于空闲状态；（2）B2C快件和O2O快件配送地址存在较高的重合度，B2C快递员的配送能力未被充分利用。然后据此提出B2C和O2O订单联合配送模式，并设计联合配送模式下配送员最优路径规划算法，最后设计算例并应用所设计的算法得到最有快递员配送路径，结果表明算法在可接受的时间内能够得到最优配送路径，且在独立配送模式下需由两位配送员才能完成的配送任务在联合配送模式下仅由一名配送员即能在所要求时间窗内完成。
参考文献：
[1]Dantzig G B， Ramser J H.The truck dispatching problem[J]. Management science， 1959， 6（1）： 80-91.
[2]Clarke G， Wright J W. Scheduling of vehicles from a central depot to a number of delivery points[J].Operations research， 1964， 12（4）： 568-581.
[3]Lenstra J K， Kan A H G. Complexity of vehicle routing and scheduling problems[J].Networks， 1981， 11（2）： 221-227.
[4]Lin S. Computer solutions of the traveling salesman problem[J]. The Bell system technical journal， 1965， 44（10）： 2245-2269.
[5]Glover F.Future paths for integer programming and links to artificial intelligence[J].Computers & operations research， 1986， 13（5）： 533-549.