论文部分内容阅读
摘 要：本文将客户满意度引入需求可拆分车辆路径问题，改进拆分策略，同时考虑最小化配送总成本和最大化客户满意度，建立考虑客户满意度的多目标SDVRPTW模型，并应用Pareto禁忌搜索算法进行求解，通过算例验证模型和算法的正确性及有效性。
关键词：需求可拆分车辆路径问题 客户满意度 Pareto禁忌搜索算法
一、引言
传统的车辆路径问题设每个任务点的需求由一辆车在一次服务中完成，即客户点需求不允许拆分。但在实际问题中，将单一客户点的需求允许由不止一辆车进行配送，更能提高车辆利用率，降低运输成本，具有现实意义。现代配送早已不是单纯追求成本最小化，提高客户满意度已成为物流企业服务的目标之一。综上所述，本文研究考虑客户满意度的需求可拆分车辆路径问题，提出适用于解决该问题的优化方法并验证其可行性，从而优化企业服务水平和经济效益两个指标。
二、问题模型
1.问题描述。针对单一配送中心和多个客户点所组成的配送网络，每个客户点坐标、可接受服务时间及需求量已知，车辆从配送中心出发，完成各客户点服务后，返回配送中心。当客户点的需求量大于车辆的剩余载重时，允许进行分割配送，即一个客户点允许不同车辆服务不止一次。完成以上任务是在客户的时间窗约束下进行的，根据车辆开始服务时间，反应客户的满意度水平。
2.模型假设。（1）每条路线上各客户的需求量之和不得超过车辆的载重限制；（2）每个客户的需求必须满足，但可以由一辆或一辆以上的车辆来满足。
3.符号和变量说明：
（1）参数符号：：，所有节点的集合，0代表车场，代表n个客户点；：车辆的满载量；：客户点的需求量；：任意两个客户点之间的距离；：车辆k到达客户点i的时间；：客户点的期望服务时间窗；：客户点的可容忍服务时间窗；：车辆行驶距离费用系数；：等待费用系数；：车辆启用成本。
（2）决策变量：
；
4.模型建立。
（1）满意度函数：
（2）目标函数：
=……（1）
=……（2）
（1）、（2）式为 SDVRPTW 的目标函数，（1）表示线路行驶总费用最小，包含车辆行驶产生的路径费用、提前到达等待费用以及车辆启用费用；（2）表示最大化客户的平均满意度。
三、Pareto禁忌搜索算法
1.初始解。用最近距离法生成初始解，先生成一组TSP初始解，再根据车辆最大载重量进行拆分形成VRP初始解。
2.邻域结构。本文采用插入（Insert）、互换（Swap）和逆序（Inverse）来产生TSP邻域解，再转化为VRP。
3.非劣解集的筛选及更新。初始非劣解的筛选是指根据生成的初始解，经过帕累托原理判断后，选择不受其他解支配的解放入非劣解集中；更新非劣解集是指当新的解不受其他当前解以及非劣解集中的非劣解支配时，把当前解放入非劣解集中。
四、算例分析
本文采用50个客户点的Solomon数据集R102作为基本数据，通过随机方法生成客户的期望时间窗。设定车载量为50，车辆单位距离运输成本为1，车辆启用成本为100，单位时间等待成本为10，车速为1。算例前10个客户的坐标及时间窗数据见表一。
3.参数设置。循环代数=500，候选解个数=300，最大迭代次数=100，禁忌表长度=10。对算例重复仿真10次，对比不拆分情况，得到结果如表二所示。
由表三可知，采用需求可拆分的策略可以降低配送车辆数，从而降低启用成本，除此之外，拆分可以明显降低等待时间成本，避免等待所产生的成本消耗，但随着满意度要求的提高，可拆分的路径成本要高于不可拆分。故企业在进行物流配送规划时，还需衡量三者关系，对比分析，从而做出合理的决策。
参考文献：
[1]Archetti， C.， M. Bouchard and G. Desaulniers， Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows[J]. Transportation Science， 2011. 45（3）： p. 285-298.
[2]朱玲， 吴迪. 需求可拆分的汽车零部件循环取货路径优化研究. 计算机应用研究， 2013， 30（6）： 1647-1651.
[3]杨鹏， 邹浩， 徐贤浩. 带时间窗集送货需求可分车辆路径问题的改进蟻群算法. 系统工程， 2015， （9）： 58-62.
关键词：需求可拆分车辆路径问题 客户满意度 Pareto禁忌搜索算法
一、引言
传统的车辆路径问题设每个任务点的需求由一辆车在一次服务中完成，即客户点需求不允许拆分。但在实际问题中，将单一客户点的需求允许由不止一辆车进行配送，更能提高车辆利用率，降低运输成本，具有现实意义。现代配送早已不是单纯追求成本最小化，提高客户满意度已成为物流企业服务的目标之一。综上所述，本文研究考虑客户满意度的需求可拆分车辆路径问题，提出适用于解决该问题的优化方法并验证其可行性，从而优化企业服务水平和经济效益两个指标。
二、问题模型
1.问题描述。针对单一配送中心和多个客户点所组成的配送网络，每个客户点坐标、可接受服务时间及需求量已知，车辆从配送中心出发，完成各客户点服务后，返回配送中心。当客户点的需求量大于车辆的剩余载重时，允许进行分割配送，即一个客户点允许不同车辆服务不止一次。完成以上任务是在客户的时间窗约束下进行的，根据车辆开始服务时间，反应客户的满意度水平。
2.模型假设。（1）每条路线上各客户的需求量之和不得超过车辆的载重限制；（2）每个客户的需求必须满足，但可以由一辆或一辆以上的车辆来满足。
3.符号和变量说明：
（1）参数符号：：，所有节点的集合，0代表车场，代表n个客户点；：车辆的满载量；：客户点的需求量；：任意两个客户点之间的距离；：车辆k到达客户点i的时间；：客户点的期望服务时间窗；：客户点的可容忍服务时间窗；：车辆行驶距离费用系数；：等待费用系数；：车辆启用成本。
（2）决策变量：
；
4.模型建立。
（1）满意度函数：
（2）目标函数：
=……（1）
=……（2）
（1）、（2）式为 SDVRPTW 的目标函数，（1）表示线路行驶总费用最小，包含车辆行驶产生的路径费用、提前到达等待费用以及车辆启用费用；（2）表示最大化客户的平均满意度。
三、Pareto禁忌搜索算法
1.初始解。用最近距离法生成初始解，先生成一组TSP初始解，再根据车辆最大载重量进行拆分形成VRP初始解。
2.邻域结构。本文采用插入（Insert）、互换（Swap）和逆序（Inverse）来产生TSP邻域解，再转化为VRP。
3.非劣解集的筛选及更新。初始非劣解的筛选是指根据生成的初始解，经过帕累托原理判断后，选择不受其他解支配的解放入非劣解集中；更新非劣解集是指当新的解不受其他当前解以及非劣解集中的非劣解支配时，把当前解放入非劣解集中。
四、算例分析
本文采用50个客户点的Solomon数据集R102作为基本数据，通过随机方法生成客户的期望时间窗。设定车载量为50，车辆单位距离运输成本为1，车辆启用成本为100，单位时间等待成本为10，车速为1。算例前10个客户的坐标及时间窗数据见表一。
3.参数设置。循环代数=500，候选解个数=300，最大迭代次数=100，禁忌表长度=10。对算例重复仿真10次，对比不拆分情况，得到结果如表二所示。
由表三可知，采用需求可拆分的策略可以降低配送车辆数，从而降低启用成本，除此之外，拆分可以明显降低等待时间成本，避免等待所产生的成本消耗，但随着满意度要求的提高，可拆分的路径成本要高于不可拆分。故企业在进行物流配送规划时，还需衡量三者关系，对比分析，从而做出合理的决策。
参考文献：
[1]Archetti， C.， M. Bouchard and G. Desaulniers， Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows[J]. Transportation Science， 2011. 45（3）： p. 285-298.
[2]朱玲， 吴迪. 需求可拆分的汽车零部件循环取货路径优化研究. 计算机应用研究， 2013， 30（6）： 1647-1651.
[3]杨鹏， 邹浩， 徐贤浩. 带时间窗集送货需求可分车辆路径问题的改进蟻群算法. 系统工程， 2015， （9）： 58-62.