| 联系我们 |
 |
合作经济与科技杂志社
地址：石家庄市建设南大街21号
邮编：050011
电话：0311-86049879 |
|
|
| 经济/产业 |
［提要］ 本文以订单为基础，从配送中心系统工程角度出发，给出追求共赢的配送路径优化算法模型，为配送中心高效运营提供新的研究思路。
关键词：共赢；配送路径；量子粒子群优化
中图分类号：F259.2 文献标识码：A
收录日期：2015年9月11日
一、引言
配送路线的合理优化属于NP（Non-deterministic Polynomial）问题，是车辆路径优化问题（VRP）中的典型问题，由Dantzig和Ramser于1959年首次提出，历经数十年的研究，已经成为运筹学与组合优化领域的研究热点课题。
二、追求共赢的配送路径系统模型
（一）客户满意度模型。传统的车辆路径问题用时间窗口作为运输服务的时间约束。结合实际，客户倾向于某一时间段内得到服务，［?子1i，?子2i］表示客户可容忍的服务时间范围，［ai，bi］为客户期望的服务时间范围，对于图中所描述的客户i其满意度函数可表示为：
?渍i（ti）=0；ti＜?子1i■-■；?子1i＜ti＜ai1；a1≤ti≤bi■-■；bi＜ti＜?子2i0；ti＞bi （1）
（二） 配送中心配送运输经济效益模型。配送中心的配送运输任务总是围绕经济效益，根据Fisher市场均衡价格的计算模型，设用m（m=1，2，…，m）辆配送车对i（i=1，2，…，n）个客户进行运输配送，每个客户持有的现金数额分别是A=｛e1，e2，…，en｝，必须支付配送车辆的服务B＝｛q1，q2，…，qm｝的费用，考虑如下一类对数收益函数：
ui（xi，1，xi，2，…，xi，m）＝■?茁i，jln（■+1） （2）
应用Lagrange乘子法，求解方程组后得：
?灼＝■ （3）
这就可以得到配送中心的配送运输的最大收入为：
Emax=maxui（xi，1，xi，2，…，xi，m）=max■?茁i，jln（■+1） （4）
其等同于：
Rmin=（max■?茁i，jln（■+1））-1 （5）
三、量子粒子群优化求解
（一）初始化种群。直接采用量子位的概率幅作为粒子（即配送车辆）当前位置的编码，其初始化编码的方案：
Pj=cos（?兹j1）sin（?兹j1）cos（?兹j2）sin（?兹j2）……cos（?兹j1）sin（?兹j1） （6）
（二）解空间变换。量子位的每个概率幅对应解空间的优化变量，记粒子Pj上第i个量子位为［?琢ij，?茁ij］■，则相应的解空间变量为：
Pjlc=（cos（?兹jl1），cos（?兹jl2），…，cos（?兹jln）） （7）
Pjls=（sin（?兹jl1），sin（?兹jl2），…，sin（?兹jln）） （8）
（三）粒子状态更新。粒子状态更新规则为：
△?兹ji（t+1）＝?棕△?兹ji（t）+c1r1（△?兹l）+c2r2（△?兹g） （9）
（四）变异处理。由量子非门实现变异操作过程。
0 11 0cos（?兹ji）sin（?兹ji）＝sin（?兹ji）cos（?兹ji）=cos（■-?兹ji）sin（■-?兹ji） （10）
其中j∈｛1，2，…，m｝，i∈｛1，2，…，n｝。
（五）粒子群的适应度。基于共赢的配送路径量子粒子群优化的适应度定义为：
Z＝?籽1■+?籽2■+?籽3■+?籽4（1-■■?渍i（ti））+■ （11）
其中，VN表示使用的车辆数，VNmin表示已知使用的最小车辆数，VNmax表示已知使用的最大车辆数，D表示车辆行驶的总距离，Dmin表示车辆最小行驶距离，Dmax表示车辆最大行驶距离，WT表示总等待时间，WTmin表示前种群中最小等待时间，WTmax表示前种群中最大等待时间，而?籽1，?籽2，?籽3，?籽4，?籽5表示权重，且?籽1+?籽2+?籽3+?籽4+?籽5＝1。
四、求解优化算例
石药乐仁堂医药物流配送中心，其主要的业务是从事药品的零售配送。配送技术指标为：年工作时间为251天（每周五日工作制），每天工作8小时（一班制），药品预计年销量40万大箱，全省内零售户数为28，000户，一周配送一次，即平均每个工作日将配送4，800个零售户，用户提供详细零售户的布局情况。用基于共赢配送路径模型进行优化，进行了为期3个月的优化计算，图1是其适应度函数的进化曲线图。（图1）优化结果：优化前原配送车辆为70辆，优化后使用56辆；优化后的路径围绕配送中心成“花瓣形”，配送中心的综合运营成本大幅度下降，单件药品的综合运行成本降至0.16元，与实际运行的效果接近。
本文基于共赢机理去思考配送路径的优化问题，兼顾对顾客、对商家的利益，可以提高配送中心建设的科学性以及提高配送中心运营质量。
（作者单位：河北交通职业技术学院）
主要参考文献：
［1］G.B.Dantzig，J.H.Ramser，The Truck Dispatching Problem.1959.
［2］贾永基.车辆调度问题优化算法研究.上海交通大学博士学位论文，2004.
［3］Ning Chen，Xiaotie Deng，Xiaoming Sun.Andrew Chi-Chih Yao：Fisher Equilibrium Price with a Class of Concave Utility Functions，ESA 2004. |
|
|
|
