量子电子学报
    主页 > 期刊导读 >

基于混合粒子群算法的车辆路径优化问题研究

来源：量子电子学报 【在线投稿】 栏目：期刊导读 时间：2021-02-24

物流科技2008年第9期LogisticsSci—TechNo．9，2008．仓储运输·Research onQPSOAlgorithm forVehicleRoutingProblem黄天赦．叶春明(iZ理IX9，上海)HUANGTian-she，YEChun-ming(University ofShanghai70rScience andTechnology,Shanghai，China)摘要：设计了一种引入了量子和遗传算法思想的粒子群算法。该算法结合了粒子群优化算法的快速寻优能力和量子算法可以同时处理多个目标的优点，避免了基本粒子群算法易陷入局部最优的缺点，提高了求解速度。该算法用于解决车辆路径问题。通过实验表明了这种算法具有较好的性能。关键词：粒子群算法；量子；遗传算法；车辆路径问题中图分类号：U116．2文献标识码：A文章编号：1002—3100 f—0026—04Abstract：The proposed particle swarm optimization(PSO)al— gorithm combines the fast optimum search ability of originalPSO with the virtue of disposing many objects at the same time of quanta algorithm．It can avoid trapping to local mini— ma as compared with originalPSO and improve the speed of solution．The proposed algorithm was applied to the vehicle routing problem．The experimental results ofQPSO on vehicle routing problem show the efficiency of the new algorithm．Key words：particle swarm optimization；quantum；genetic al— gorithm；vehicle routing problem0引言物流配送是物流企业日常生产中一个非常重要的环节，其效率高低直接影响物流企业的运作效益，同时也是电子商务活动不可缺少的内容。在配送管理中，经常需要决策的一个问题就是如何寻找一组费用最小的车辆径路，将货物配送到每个客户手中，也即所谓的车辆路线问题(VehicleRoutingProblem，VRP)。自1959年由Dantzing和Ramser首次提出VRP以来，很快引起运筹学、应用数学、网络分析、图论及计算机应用等学科的专家与运输计划制定者和管理者的极大重视。因为配送路线是否合理，对加快配送速度、降低配送成本、提高服务质量及增加总体经济效益影响较大。因此，采用科学合理的方法确定配送线路是配送业务中一项非常重要的工作。VRP一般定义为：对一系列发货点或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制及时间限制等)下，达到一定的目标(如路程最短、费用最小、时间尽量少及使用车辆尽量少等)。配送路径安排是一个NP—hard问题，很难找到此问题的精确解，常用的一类启发式算法有：一般启发式算法、神经网络、遗传算法、禁忌搜索及模拟退火等智能化启发式算法。粒子群优化算法是一种模拟鸟群飞行的群体智能算法，具有个体数目少，计算简便，容易实现等优点，在连续空间的优化上取得了非常好的效果，由于VRP问题是一个离散的问题，因此本文设计了一种混合粒子群算法，通过实验证明这种方法在解决VRP问题时有较好的效果。1VRP问题的数学模型VRP问题在现实中的一个物流系统可由这几部分组成：服务区、仓库、分布在服务区内的服务点。要把这样的一个经典的VRP问题抽象成一个数学模型，需要设定一些前提：只有一个仓库，所有车辆从这里装载货物出发，运送完货物返回仓库：所有的车辆的运输能力都是一样的；每一个服务点只能由一辆车提供服务。．设配送中心需向L个客户送货，每个客户的货物需求量是g，每辆车的载重量是q，ci表示从i点到／点的运输成本，其含义可以是距离、费用、时间等，设配送中心编码为0，客户编码为1，2，…正，数学模型如下。『1，车辆k由客户i行驶到客户j”【0．否则 f1．客户i的任务由车辆k完成～【0．否则收稿日期：2008—04—17作者简介：黄天赦(1984一)，男，湖北武汉人，上海理_Y-大学管理学院管理科学与工程专业硕士研究生，研究方向：工业工程叶春明(1964一)，男，安徽宣城人，上海理工大学管理学院，教授，博士研究生导师，研究方向：管理科学与工程。26 f，{)dsⅢ“S·}I_h、(·h?()08 i)基于混合粒子群算法的车辆路径优化问题研究建立数学模型，．LK minz_∑∑∑c勘 i=Oj=0K=I^∑giYi女≤g，k=l“2一，K=】(1)(2)荟K舻出》一…㈩∑石珊砜j=1，2，…，L；七=1，2，…，K(4)∑Xijk=Yj。乩2，…，￡；％=l，2，…，K(5)戈腓=O或1 iJ=l，2，…，L；k=l，2，…，K(6)Yjk=0或1 i=1，2，…，L；k=l，2，…，K(7)其中，目标式(1)保证了总成本Z最小；式(2)为车辆的容量约束；式(3)保证了每个客户点的运输任务仅由一辆车来完成，而所有的运输任务则由K辆车共同完成；式(4)和式(5)保证每个客户能且只能被一辆车服务一次。2粒子群算法简介2．1基本的粒子群算法粒子群算法采用的是速度一位置搜索模型。在PSO系统中，每个备选解被称为一个粒子，多个粒子共存、合作寻优，每个粒子根据它自身的经验和相邻群体的最佳经验在问题空间向更好的位置飞行，直至搜索到最优解。每个粒子代表一个候选解，解的优劣由最优化的目标函数决定。其计算公式如下：V【]=伽丰鄯lI+cl木rand()(pbest【J—戈『1)+c2术rand()(gbest【l一戈l1) x【I=戈【l抑IJ其中埘称为惯性因子，控制以前速度对当前速度的影响，较大的训适于对解空间进行大范围探查，较小的W适于进行小范围开挖。cl和c2是正常数，称为加速因子，rand是两个独立的(0，1)之间的随机数。gbest是当前粒子的全局最优值， pbest是某个粒子个体最优值。2．2编码、编码方式，初始解的设置对组合优化问题的求解都有很大的影响。一般情况下，客户的编码方式是用自然数表示，自然数 i表示第i个客户(0则代表仓库)。本文采用一种新的编码表示方式，即对于k个客户、m辆车的VRP问题，在客户序列中插入m一1个0，这样把客户序列分成m段，每一段代表一辆车的行走路径。每个微粒即对应一个南+m—l维向量，也就是问题一个解。例如，设VRP问题有车辆3辆，6个客户，若某粒子的位置向量x为：表示的路径为：第1辆车：0—5—3—0第2辆车：0—6—1—4—0第3辆车：0—2—0这样的编码方式有效地解决了车辆的编码，而且将VRP转成一个TSP问题，便于采用传统TSP问题处理方法来求解VRP问题。基本粒子群算法中，粒子下一个位置是通过速度的更新来进行的。本文中，下一个位置是通过与全局极值和个体极值的交叉，最后再变异产生的。同时经过变异还防止了算法陷入局部极值的可能。3混合粒子群算法的介绍3．1量子计算的基础知识3．1．1量子比特编码一个量子比特(quantum bit or qubit)不仅可以表示“O”或“1”两种状态，而且可以同时表示这两种状态之问的任意中间态。一般地，用m个量子比特就可以同时表示2m个状态。一个量子比特可能处于11)或10)，或者处于11)和10)之间的中间态，即11)和10)的不同叠加态，因此一个量子位的状态可表示为：I沙)=d10)书11)其中O／和卢可以是复数，表示相应状态的概率幅，且满足下列归一化条件：Icd一+归I‘=1在式(2)中，ldI‘表示J0)的概率，蚓。表示11)的概率。1．。l：叠…一～o’h《}{|：=_州端q27基于混合粒子群算法的车辆路径优化问题研究采用量子比特系统编码多态问题时，具有更好的多样性特征，例如其中Id。12+归。12=1，i=1，2，…，m，可同时代表2…种状态。3．1．2量子角一个量子角(quantum angle)为一任意角度值0，此时一个量子比特可以由量子角表示为：[Q】等价为原有量子比特表示，即：(p)I)(口)1)或『8in‘口’1，此时sin(0)和cos(O)分别表示相应态的概率振幅。Isin(010}=sin+COS sin0Isin0)12表示量子比特在…0，态时即：(p)I)(口)1)或lI，此时)和)分别表示相应态的概率振幅。)I‘表示量子比特在…’态时【COS(0)J的概率，Icos(p)l。表示量子比特在“1”态时的概率，且自然满足kin(p)I‘+lcos(0)I一=1。3．1．3量子门的更新量子门(quantum gate)是量子比特的调整元件，可根据具体问题选择所需要的量子门，通用量子旋转门调整策略式：[主]=u c臼，[言]=。c。ions。(口O，)。-。s。in。口(O，’][盖] p=【f(△口)+只J3．2混合粒子群算法的程序设计(1)随机产生初始种群，也即初始解，个数为n，给每个变量赋值，W，cl，c2，迭代次数r，每个客户的需求量g，车辆载重 q，客户数目￡，车辆数目m。(2)计算初始粒子的适应值，记录当前粒子的适应值为个体极值pbest，取其中最优值为群体极值gbest。(3)初始化Q‘(量子门)；先将式(1)的数值设为—兰，则对于每一个量子比特来说，取某一状态的概率都相同。、／2(4)每个粒子用下面的公式更新速度和量子角：V。(t+1)=训半V。(f)+cf半rand()术(pbest。叫。(t))+c2球rand()木(驴est一戈，(f’)0．(f+1)=q(t)+矿。(f+1)用得到的量子角更新量子门：麟：]=[荔㈧署爿嵫：](5)将Q‘转为F；虽然量子比特可以表征多种状态，但在受到观测后，将坍缩到一个定态，即根据概率生成一个解。将量子比特转换为二进制编码的过程是随机产生一个[0，1】数，若它大于h。l。，取1，否则，取0，每个粒子对应一个户。(6)对每个粒子的户进行判断，若该位置为1，则对应的粒子的该位与全局最优粒子进行交叉，交叉方法是：取粒子某个位置的值，若它与要交叉的对象在该位不相等，则粒子这个位置的值等于要交叉的对象在该位的值，若相等则不交叉；交叉完后粒子会有两个位置的值一样，则将另一个位置的值换为交叉时的那个值，例如：取的第4位进行交叉与5432 l，则交叉后的结果为l4325。(7)将第一次交叉后的结果按∥规则与该粒子的最优状态进行交叉，交叉方法同前。(8)将交叉后的结果进行变异，方法是，从粒子中随机取两个位置，然后将包括这两个位置在内的子序列以反方向插入到原来位置。(9)将交叉完后的粒子进行判断，若满足条件，则作为粒子的下一个位置，并计算适应值，、i’；若不满足则回到步骤(5)。(10)比较每个粒子新适应值与其个体极值的大小，若f(i)