论文部分内容阅读
摘要：卷烟配送普遍呈现客户点多、路线复杂的特点，是典型的组合NP难题。以配送成本最低且配送量均衡为优化目标，建立带时间窗的卷烟配送通用数学模型；引入选择与交叉操作，提出运用改进的遗传量子粒子群算法（GQPSO）实现车辆编号和配送次序同步寻优，以制定卷烟配送的最优策略。实例表明：GQPSO能快速有效制定满足优化目标的卷烟配送策略。
关键词：卷烟配送；组合非线性优化；成本最低；配送量均衡；遗传量子粒子群算法
中图分类号：F760.3文献标识码：A
Abstract: Tobacco delivery, characterized by excessive delivery points and complicated delivery routes, is a typical combined Nondeterministic Polynomial（NP）problem. With the minimal delivery cost and balanced carrying to be target, the common tobacco delivery mathematic model with time window is built. A modified Genetic Quantum-behaved Particle Swarm Optimization（GQPSO）based on the selection and hybridization is designed to solve the optimal delivery routes, which can optimize the vehicle numbers and delivery orders together. The example shows that GQPSO can design the tobacco delivery routes fast, optimally and effectively.
Key words: tobacco delivery; combined nonlinear optimization; minimized cost; balanced carrying; GQPSO
粒子群优化算法（Particle Swarm Optimization, PSO）是Kennedy等于1995年提出的一种收敛快、非劣解质量高、鲁棒性好的全局优化算法，广泛应用于参数寻优、模式分类、路径优化等方面[1]。但是PSO仍具有早熟、后期效率不高、易陷入局部最优等缺陷。为改进算法性能，Angeline等[2]提出一种智能PSO算法；Bergh[3]提出局部收敛的GCPSO和协同进化的CPSO；Liang[4]提出三种粒子优化策略（ELPSO、MLPSO、CLPSO）；Sun[5]则提出了量子粒子群算法（QPSO）等。其中QPSO具有控制参数少、设置简单的优点，实验表明其全局性能远优于标准PSO[6]。但是，QPSO粒子分布比PSO更离散，粒子的协同进化放慢了收敛过程，粒子数少时更易陷入局部最优。
卷烟配送是包含多个目标协调优化的车辆路径问题，具有配送点多、位置零散、配送任务繁杂的特点，采用科学有效的方法确定配送策略是一项非常重要的工作。在研究QPSO的基础上，本文提出运用改进的遗传量子粒子群算法（GQPSO）来求解市卷烟配送多目标非线性组合优化问题的最优配送策略。
1带时间窗的卷烟配送问题建模
1.1问题描述
我国幅员辽阔，各地地形地貌、交通情况、人口密度和货源分布等各不相同，通常卷烟配送流程如图1所示。
可以看出，卷烟配送主要包括两种模式：“一级配一级送”和“一级配二级送”。前者适用于地（市）所辖周边范围的配送，后者则适用于范围较大、交通不便、线路迂回的县区内的配送。
1.2模型建立
作如下界定：（1）仅一个配送中心，车辆从配送中心出发，完成任务后返回配送中心；（2）卷烟零售客户的平均需求量已知；（3）由单车完成单户的配送；（4）车辆总数已知且单人单车。定义：
Θ■■=■（1）
Θ■■=■（2）
车辆数是决定配送成本的关键因素，可在模型中进行优化。考虑用车数的卷烟配送问题可描述为：配送中心有m辆车，装载量分别为Q=Q■,Q■,…,Q■■，在一个周期内零售户的需求量为D=D■,D■,…,D■■，则满足：∑D■≤∑Q■。若车m■需对n■个零售户进行配送，则满足：∑D■≤Q■。若配送中心为W■，零售户记为W■,W■,…,W■，以W■表示路径总和，m■是参与车辆数m■≤m，ω是路径成本函数，则J■=ωW■,m■最优表示配送成本最小；若L=l■,l■,…,l■■各量对应各车载货量，I■为m■维全1列向量，则J■=||I■D■I■-m■L||■m■表示配送量均衡。若s■为车辆到达时间，a■,b■为零售户i的经营时间，p■和p■分别为客户等待和滞留成本，λ为松弛因子，则带时间窗的卷烟配送数学模型为：
■J=ωW■,m■+λ·||I■D■I■-m■L||■m■+■p■,p■·■ （3）
s.t.■ （4）
2量子粒子群算法的优化机理
2.1标准粒子群算法
D维空间中，G个粒子种群为X=X■,X■,…,X■，第i个粒子的位置表示为X■=X■,X■,…,X■■。根据X■计算目标函数可得到适应值。第i个粒子的速度为V■=V■,V■,…,V■■, P■=P■,P■,…,P■■为个体最优适应度位置、P■=P■,P■,…,P■■为种群的最优适应度位置。粒子通过个体极值和全局极值进行更新：
v■■=w■V■■+c■r■c■r■P■■-X■■P■■-X■■■（5）
X■■=X■■+V■■ （6）
其中d=1,2,…,D, i=1,2,…,G, k为进化代数，w■为惯性权重，c■和c■为学习因子，r■和r■为0,1间的随机数。
2.2量子粒子群算法
与PSO不同，QPSO的粒子只更新位置信息，即：
X■■=P■■±L■■lnu（7）
其中u为0,1间的随机数，p■■和L■■为[5,6]：
P■■=φ·P■■+1-φ·P■■ （8）
L■■=β■m■■-X■■（9）
其中β■为收缩系数，m■■为种群平均最好位置，即：
β■=1-1-αkT■ （10）
m■■=■■=■■P■■,■P■■,…,■P■■■（11）
由此更新的粒子为：
X■■=P■■±β■m■■-X■■lnu（12）
PSO进化速度比较有限，搜索空间不能覆盖整个可行域。而QPSO引入位置随机指数变更，可保证量子空间的粒子以一定的概率出现在整个可行解空间。
3改进遗传量子粒子群算法
3.1算法设计
结合式（8）和式（12）可知：
X■■=φ·P■■-P■■+P■■±L■■lnu（13）
当粒子进化至较小空间时，P■■、P■■将可能非常接近，L■■将趋于零，极大地削弱了粒子的量子行为。尤其对于高维非线性卷烟配送问题，较少的粒子易导致种群多样性缺失，从而陷入局部最优。
借鉴遗传算法的组合交叉思想，通过粒子交叉产生代表新解集的种群。首先将适应度值排序，整个种群分成K个家族；然后在每个家族中随机选择一个粒子组成子种群。子种群的粒子两两随机配对进行交叉，以x表示子种群的粒子，则后代的位置和速度为：
Child■x=p×Parent■x+1-p×Parent■x（14）
Child■x=p×Parent■x+1-p×Parent■x（15）
Child■v=■×Parent■v（16）
Child■v=■×Parent■v（17）
其中Child和Parent代表子代和父代粒子，p为0,1上的随机向量。选择子代和父代适应度高的进入下一代。
引入选择与交叉操作，后代可继承双亲粒子的优点，理论上加强了粒子的区域搜索能力；而交叉操作可控制双亲的海明距离，避免了近亲繁殖，有助于保持种群的多样性。
3.2计算模型构建
对于n维带时间窗的卷烟配送问题，主要需优化各配送次序和配送车辆，而本文提出图2所示算法结构实现两高维参数的同步寻优。
车辆编号为1,2,…,m，配送次序编号为1,2,…,n■i=1,2,…,m。初始化车辆编号M和配送次序N分别为1,m和1,n上的随机整数向量，速度M■和N■为-m+1,m-1和-n+1,n-1上的随机实数，迭代后分别取整。则M中标记为i的元素，N中对应编号大小即表示车辆i的配送次序。各粒子同时表达配送次序N和车辆编号M的信息，共同决定粒子对评价指标的适应度。
4计算与仿真
某市卷烟配送中心共有6辆车，工作时间为8:00至17:00，装卸货均需半小时，形成网络如图3所示。
各零售户的需求量如表1所示。
依次取种群规模为20、30、50和80，最大迭代次数为800，粒子适应度初始化为10 000，c■=c■=1.49445。分别采用PSO、QPSO和GQPSO计算100次，结果分析如表2所示，计算得知最优配送车辆数为3。
种群中最优粒子适应度收敛曲线如图4所示。
根据最优粒子信息得到最优的配送路径如表3所示，其中“*”表示需配送的零售户。
结合表2和图4可知，相比PSO和QPSO，在种群粒子较少时GQPSO能够更有效地求解多目标卷烟配送的最优化策略；随着粒子数增多，三种算法的优化性能均有所提高，但GQPSO在整个过程中全局优化性较好，收敛时间明显优于PSO和QPSO。由表3可知，最短配送里程为459km，配送量最大偏差为4件，配送任务均可在工作时间内完成。
5结论
卷烟配送普遍存在配送点多、配送网络复杂的特点。本文以单位配送周期内的配送成本最低且配送量均衡为优化目标，建立了带时间窗的卷烟配送问题的通用数学模型，并提出采用改进遗传量子粒子群算法来求解该多目标组合优化问题。结合某市卷烟配送实例计算表明：GQPSO能够以配送量均衡、配送成本最低最优，计算出在客户工作时间内完成的卷烟配送策略，是解决卷烟配送组合优化问题的有效方法。
参考文献：
[1] 杨传将，刘清，黄珍. 一种量子粒子群算法的改进方法[J]. 计算技术与自动化，2009,28(1):100-103.
[2]Angeline P. J.. Using Selection to Improve Particle Swarm Optimization[R]. IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, 1998.
[3]Bergh F, Engelbrecht A. P.. A new locally convergent particle swarm optimizer[C] // In IEEE Conference on Systems, Man and Cybernetics, 2002.
[4]Liang J, Suganthan A, Baskar S.. Particle swarm optimization algorithms with novel learning strategies[C] // IEEE Interna- tional Conference on Systems, Man, Cybernetics, 2004.
[5]Sun J, Feng B, Xu W. B.. Particle swarm optimization with particles having quantum behavior[C] // Proc. of 2004 Congress on Evolutionary Computation, 2004.
[6] 沈佳宁，须文波，徐文龙. QPSO多目标优化算法解约束规划问题[J]. 微计算机信息，2009,25(3):236-237.
关键词：卷烟配送；组合非线性优化；成本最低；配送量均衡；遗传量子粒子群算法
中图分类号：F760.3文献标识码：A
Abstract: Tobacco delivery, characterized by excessive delivery points and complicated delivery routes, is a typical combined Nondeterministic Polynomial（NP）problem. With the minimal delivery cost and balanced carrying to be target, the common tobacco delivery mathematic model with time window is built. A modified Genetic Quantum-behaved Particle Swarm Optimization（GQPSO）based on the selection and hybridization is designed to solve the optimal delivery routes, which can optimize the vehicle numbers and delivery orders together. The example shows that GQPSO can design the tobacco delivery routes fast, optimally and effectively.
Key words: tobacco delivery; combined nonlinear optimization; minimized cost; balanced carrying; GQPSO
粒子群优化算法（Particle Swarm Optimization, PSO）是Kennedy等于1995年提出的一种收敛快、非劣解质量高、鲁棒性好的全局优化算法，广泛应用于参数寻优、模式分类、路径优化等方面[1]。但是PSO仍具有早熟、后期效率不高、易陷入局部最优等缺陷。为改进算法性能，Angeline等[2]提出一种智能PSO算法；Bergh[3]提出局部收敛的GCPSO和协同进化的CPSO；Liang[4]提出三种粒子优化策略（ELPSO、MLPSO、CLPSO）；Sun[5]则提出了量子粒子群算法（QPSO）等。其中QPSO具有控制参数少、设置简单的优点，实验表明其全局性能远优于标准PSO[6]。但是，QPSO粒子分布比PSO更离散，粒子的协同进化放慢了收敛过程，粒子数少时更易陷入局部最优。
卷烟配送是包含多个目标协调优化的车辆路径问题，具有配送点多、位置零散、配送任务繁杂的特点，采用科学有效的方法确定配送策略是一项非常重要的工作。在研究QPSO的基础上，本文提出运用改进的遗传量子粒子群算法（GQPSO）来求解市卷烟配送多目标非线性组合优化问题的最优配送策略。
1带时间窗的卷烟配送问题建模
1.1问题描述
我国幅员辽阔，各地地形地貌、交通情况、人口密度和货源分布等各不相同，通常卷烟配送流程如图1所示。
可以看出，卷烟配送主要包括两种模式：“一级配一级送”和“一级配二级送”。前者适用于地（市）所辖周边范围的配送，后者则适用于范围较大、交通不便、线路迂回的县区内的配送。
1.2模型建立
作如下界定：（1）仅一个配送中心，车辆从配送中心出发，完成任务后返回配送中心；（2）卷烟零售客户的平均需求量已知；（3）由单车完成单户的配送；（4）车辆总数已知且单人单车。定义：
Θ■■=■（1）
Θ■■=■（2）
车辆数是决定配送成本的关键因素，可在模型中进行优化。考虑用车数的卷烟配送问题可描述为：配送中心有m辆车，装载量分别为Q=Q■,Q■,…,Q■■，在一个周期内零售户的需求量为D=D■,D■,…,D■■，则满足：∑D■≤∑Q■。若车m■需对n■个零售户进行配送，则满足：∑D■≤Q■。若配送中心为W■，零售户记为W■,W■,…,W■，以W■表示路径总和，m■是参与车辆数m■≤m，ω是路径成本函数，则J■=ωW■,m■最优表示配送成本最小；若L=l■,l■,…,l■■各量对应各车载货量，I■为m■维全1列向量，则J■=||I■D■I■-m■L||■m■表示配送量均衡。若s■为车辆到达时间，a■,b■为零售户i的经营时间，p■和p■分别为客户等待和滞留成本，λ为松弛因子，则带时间窗的卷烟配送数学模型为：
■J=ωW■,m■+λ·||I■D■I■-m■L||■m■+■p■,p■·■ （3）
s.t.■ （4）
2量子粒子群算法的优化机理
2.1标准粒子群算法
D维空间中，G个粒子种群为X=X■,X■,…,X■，第i个粒子的位置表示为X■=X■,X■,…,X■■。根据X■计算目标函数可得到适应值。第i个粒子的速度为V■=V■,V■,…,V■■, P■=P■,P■,…,P■■为个体最优适应度位置、P■=P■,P■,…,P■■为种群的最优适应度位置。粒子通过个体极值和全局极值进行更新：
v■■=w■V■■+c■r■c■r■P■■-X■■P■■-X■■■（5）
X■■=X■■+V■■ （6）
其中d=1,2,…,D, i=1,2,…,G, k为进化代数，w■为惯性权重，c■和c■为学习因子，r■和r■为0,1间的随机数。
2.2量子粒子群算法
与PSO不同，QPSO的粒子只更新位置信息，即：
X■■=P■■±L■■lnu（7）
其中u为0,1间的随机数，p■■和L■■为[5,6]：
P■■=φ·P■■+1-φ·P■■ （8）
L■■=β■m■■-X■■（9）
其中β■为收缩系数，m■■为种群平均最好位置，即：
β■=1-1-αkT■ （10）
m■■=■■=■■P■■,■P■■,…,■P■■■（11）
由此更新的粒子为：
X■■=P■■±β■m■■-X■■lnu（12）
PSO进化速度比较有限，搜索空间不能覆盖整个可行域。而QPSO引入位置随机指数变更，可保证量子空间的粒子以一定的概率出现在整个可行解空间。
3改进遗传量子粒子群算法
3.1算法设计
结合式（8）和式（12）可知：
X■■=φ·P■■-P■■+P■■±L■■lnu（13）
当粒子进化至较小空间时，P■■、P■■将可能非常接近，L■■将趋于零，极大地削弱了粒子的量子行为。尤其对于高维非线性卷烟配送问题，较少的粒子易导致种群多样性缺失，从而陷入局部最优。
借鉴遗传算法的组合交叉思想，通过粒子交叉产生代表新解集的种群。首先将适应度值排序，整个种群分成K个家族；然后在每个家族中随机选择一个粒子组成子种群。子种群的粒子两两随机配对进行交叉，以x表示子种群的粒子，则后代的位置和速度为：
Child■x=p×Parent■x+1-p×Parent■x（14）
Child■x=p×Parent■x+1-p×Parent■x（15）
Child■v=■×Parent■v（16）
Child■v=■×Parent■v（17）
其中Child和Parent代表子代和父代粒子，p为0,1上的随机向量。选择子代和父代适应度高的进入下一代。
引入选择与交叉操作，后代可继承双亲粒子的优点，理论上加强了粒子的区域搜索能力；而交叉操作可控制双亲的海明距离，避免了近亲繁殖，有助于保持种群的多样性。
3.2计算模型构建
对于n维带时间窗的卷烟配送问题，主要需优化各配送次序和配送车辆，而本文提出图2所示算法结构实现两高维参数的同步寻优。
车辆编号为1,2,…,m，配送次序编号为1,2,…,n■i=1,2,…,m。初始化车辆编号M和配送次序N分别为1,m和1,n上的随机整数向量，速度M■和N■为-m+1,m-1和-n+1,n-1上的随机实数，迭代后分别取整。则M中标记为i的元素，N中对应编号大小即表示车辆i的配送次序。各粒子同时表达配送次序N和车辆编号M的信息，共同决定粒子对评价指标的适应度。
4计算与仿真
某市卷烟配送中心共有6辆车，工作时间为8:00至17:00，装卸货均需半小时，形成网络如图3所示。
各零售户的需求量如表1所示。
依次取种群规模为20、30、50和80，最大迭代次数为800，粒子适应度初始化为10 000，c■=c■=1.49445。分别采用PSO、QPSO和GQPSO计算100次，结果分析如表2所示，计算得知最优配送车辆数为3。
种群中最优粒子适应度收敛曲线如图4所示。
根据最优粒子信息得到最优的配送路径如表3所示，其中“*”表示需配送的零售户。
结合表2和图4可知，相比PSO和QPSO，在种群粒子较少时GQPSO能够更有效地求解多目标卷烟配送的最优化策略；随着粒子数增多，三种算法的优化性能均有所提高，但GQPSO在整个过程中全局优化性较好，收敛时间明显优于PSO和QPSO。由表3可知，最短配送里程为459km，配送量最大偏差为4件，配送任务均可在工作时间内完成。
5结论
卷烟配送普遍存在配送点多、配送网络复杂的特点。本文以单位配送周期内的配送成本最低且配送量均衡为优化目标，建立了带时间窗的卷烟配送问题的通用数学模型，并提出采用改进遗传量子粒子群算法来求解该多目标组合优化问题。结合某市卷烟配送实例计算表明：GQPSO能够以配送量均衡、配送成本最低最优，计算出在客户工作时间内完成的卷烟配送策略，是解决卷烟配送组合优化问题的有效方法。
参考文献：
[1] 杨传将，刘清，黄珍. 一种量子粒子群算法的改进方法[J]. 计算技术与自动化，2009,28(1):100-103.
[2]Angeline P. J.. Using Selection to Improve Particle Swarm Optimization[R]. IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, 1998.
[3]Bergh F, Engelbrecht A. P.. A new locally convergent particle swarm optimizer[C] // In IEEE Conference on Systems, Man and Cybernetics, 2002.
[4]Liang J, Suganthan A, Baskar S.. Particle swarm optimization algorithms with novel learning strategies[C] // IEEE Interna- tional Conference on Systems, Man, Cybernetics, 2004.
[5]Sun J, Feng B, Xu W. B.. Particle swarm optimization with particles having quantum behavior[C] // Proc. of 2004 Congress on Evolutionary Computation, 2004.
[6] 沈佳宁，须文波，徐文龙. QPSO多目标优化算法解约束规划问题[J]. 微计算机信息，2009,25(3):236-237.