论文部分内容阅读
摘要：论文在建立物流配送路径优化问题的数学模型的基础上，构造了求解该问题的粒子群优化算法。计算结果表明可以有效地求得问题的最优解。
关键词：物流配送 粒子群优化算法 优化
▲▲ 一、引言
随着市场经济的发展和物流技术专业化水平的提高，物流配送是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人。本文讨论其中的物流配送路径优化问题，配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径优化问题是一个NP难题，只有在需求点和路段较少时，才能求得精确解。粒子群优化算法的出现为求解物流配送路径优化问题提供了新的工具，尤其适用于处理传统搜索方法难于解决的复杂和非线性的问题，本文针对物流配送路径优化问题的特点，构造了求解该问题的粒子群优化算法，通过实验计算，得到了较好的结果。
▲▲ 二、物流配送路径优化问题的数学模型
物流配送路径优化描述为：从配送中心用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，要求合理安排汽车路线，使总运距最短，并满足以下条件：（1）每条配送路径上各需求点的需求量之和不超过汽车载重量；（2）每条配送路径的长度不超过汽车一次配送的最大行驶距离；（3）每个需求点的需求必须满足，且只能由一辆汽车送货。本文借鉴文献[3]建立的车辆路径问题的数学模型，并通过考虑上述物流配路径优化问题的约束条件和优化目标，建立了物流配送路径优化问题的数学模型[2]。
▲▲ 三、物流配送路径优化问题的粒子群优化算法
（1）编码方法的确定。根据物流配送路径优化问题的特点，用0表示配送中心，用1、2、···、L表示各需求点。由于在配送中心有K辆汽车，则最多存在K条配送路径，每条配送路径都始于配送中心，也终于配送中心，为了在编码中反映车辆配送的路径，作者巧妙地采用了增加K-1个虚拟配送中心的方法，分别用L+1、L+2、···、L+K-1表示。这样，1、2、···、L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个体，并对应一种配送路径方案。例如，对于一个有7个需求点，用3辆汽车完成配送任务的问题，则可用1、2、···、9（8、9表示配送中心）这9个自然数的随机排列，表示物流配送路径方案。如个体129638547表示的的配送路径方案为：路径1：0-1-2-9（0），路径2：9（0）-6-3-8（0），路径3：8（0）-5-4-7-0，共有3条配送路径；个体573894216表示的配送路径方案为：路径1：0-5-7-3-8（0），路径2：9（0）-4-2-1-6-0，共有2条配送路径。
（2）初始群体的确定。随机产生一种1~L+K-1这L+K-1个互不重复的自然数的排列，即形成一个个体。设群体规模为N，则通过随机产生N个这样的个体，即形成初始群体。
（3）适应度评估。对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函数值。本文根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件。为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体对应一个可行解），其目标函数值为Zj，则该个体的适应度Fj可用下式表示： Fj=1/（Zj+Mj×G） （9）
式中，G为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的正数。
▲▲ 四、实验计算与结果分析
本文用C语言编程，并对文献[3]列出的一个某配送中心使用2辆汽车对8个需求点进行送货的物流配送路径优化问题实例进行了实验计算。设汽车的载重量为8t，每次配送的最大行驶距离为40km，配送中心与各需求点之间、各需求点相互之间的距离及各需求点的需求量见资料[3]。
根据上述实例的特点，作者在实验计算中采用了以下参数：对上述问题，利用计算机随机求解10次，得到的计算结果见表2。
从表中数据可以看出，10次运行得到的结果均优于节约法所得的结果79.5km。而且第5次还得到了该问题的最优解67.5km，其对应的配送路径方案为：路径1：0-4-7-6-0；路径2：0-2-8-5-3-1-0。可见，利用粒子群优化算法可以方便有效地求得物流配送路径优化问题的最优解。
▲▲ 五、结论
本文在物流配送路径优化问题上构造了求解物流配送路径优化问题的粒子群优化算法。实验结果表明，可以求得最优解。
参考文献：
[1]蔡希贤，夏士智. 物流合理化的数量方法[M]. 武汉：华中工学院出版社，1985.
[2陈国良，王煦法，庄镇泉，王东生. 粒子群优化算法及其应用[M]. 北京：人民邮电出版社，1996.
[3]姜大立，杨西龙，杜文，周贤伟. 车辆路径问题的粒子群优化算法研究[J]. 系统工程理论与实践，1999（6），p40~44.
（责任编辑：段玉）
关键词：物流配送 粒子群优化算法 优化
▲▲ 一、引言
随着市场经济的发展和物流技术专业化水平的提高，物流配送是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人。本文讨论其中的物流配送路径优化问题，配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径优化问题是一个NP难题，只有在需求点和路段较少时，才能求得精确解。粒子群优化算法的出现为求解物流配送路径优化问题提供了新的工具，尤其适用于处理传统搜索方法难于解决的复杂和非线性的问题，本文针对物流配送路径优化问题的特点，构造了求解该问题的粒子群优化算法，通过实验计算，得到了较好的结果。
▲▲ 二、物流配送路径优化问题的数学模型
物流配送路径优化描述为：从配送中心用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，要求合理安排汽车路线，使总运距最短，并满足以下条件：（1）每条配送路径上各需求点的需求量之和不超过汽车载重量；（2）每条配送路径的长度不超过汽车一次配送的最大行驶距离；（3）每个需求点的需求必须满足，且只能由一辆汽车送货。本文借鉴文献[3]建立的车辆路径问题的数学模型，并通过考虑上述物流配路径优化问题的约束条件和优化目标，建立了物流配送路径优化问题的数学模型[2]。
▲▲ 三、物流配送路径优化问题的粒子群优化算法
（1）编码方法的确定。根据物流配送路径优化问题的特点，用0表示配送中心，用1、2、···、L表示各需求点。由于在配送中心有K辆汽车，则最多存在K条配送路径，每条配送路径都始于配送中心，也终于配送中心，为了在编码中反映车辆配送的路径，作者巧妙地采用了增加K-1个虚拟配送中心的方法，分别用L+1、L+2、···、L+K-1表示。这样，1、2、···、L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个体，并对应一种配送路径方案。例如，对于一个有7个需求点，用3辆汽车完成配送任务的问题，则可用1、2、···、9（8、9表示配送中心）这9个自然数的随机排列，表示物流配送路径方案。如个体129638547表示的的配送路径方案为：路径1：0-1-2-9（0），路径2：9（0）-6-3-8（0），路径3：8（0）-5-4-7-0，共有3条配送路径；个体573894216表示的配送路径方案为：路径1：0-5-7-3-8（0），路径2：9（0）-4-2-1-6-0，共有2条配送路径。
（2）初始群体的确定。随机产生一种1~L+K-1这L+K-1个互不重复的自然数的排列，即形成一个个体。设群体规模为N，则通过随机产生N个这样的个体，即形成初始群体。
（3）适应度评估。对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函数值。本文根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件。为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体对应一个可行解），其目标函数值为Zj，则该个体的适应度Fj可用下式表示： Fj=1/（Zj+Mj×G） （9）
式中，G为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的正数。
▲▲ 四、实验计算与结果分析
本文用C语言编程，并对文献[3]列出的一个某配送中心使用2辆汽车对8个需求点进行送货的物流配送路径优化问题实例进行了实验计算。设汽车的载重量为8t，每次配送的最大行驶距离为40km，配送中心与各需求点之间、各需求点相互之间的距离及各需求点的需求量见资料[3]。
根据上述实例的特点，作者在实验计算中采用了以下参数：对上述问题，利用计算机随机求解10次，得到的计算结果见表2。
从表中数据可以看出，10次运行得到的结果均优于节约法所得的结果79.5km。而且第5次还得到了该问题的最优解67.5km，其对应的配送路径方案为：路径1：0-4-7-6-0；路径2：0-2-8-5-3-1-0。可见，利用粒子群优化算法可以方便有效地求得物流配送路径优化问题的最优解。
▲▲ 五、结论
本文在物流配送路径优化问题上构造了求解物流配送路径优化问题的粒子群优化算法。实验结果表明，可以求得最优解。
参考文献：
[1]蔡希贤，夏士智. 物流合理化的数量方法[M]. 武汉：华中工学院出版社，1985.
[2陈国良，王煦法，庄镇泉，王东生. 粒子群优化算法及其应用[M]. 北京：人民邮电出版社，1996.
[3]姜大立，杨西龙，杜文，周贤伟. 车辆路径问题的粒子群优化算法研究[J]. 系统工程理论与实践，1999（6），p40~44.
（责任编辑：段玉）