有时间窗的开放式车辆调度问题的粒子群优化方法

摘要

一种有时间窗的开放式车辆调度问题的粒子群优化方法，有时间窗的开放式车辆调度问题是非常复杂的问题，通常是多约束、多目标、随机不确定优化问题。求解过程的计算量随问题的规模呈指数增长，已被证明是NP完全问题。本发明采用粒子群算法，并使用改进的廉价插入启发式算法(Cheapest Insert Algorithm)优化车辆内客户的顺序。本发明提供一种算法简单、同时具备较快的计算速度和较高的算法精度的有时间窗的开放式车辆调度问题的粒子群优化方法。

主权项

1、一种有时间窗的开放式车辆调度问题的粒子群优化方法，所述的方法主要包括以下步骤：(1)、从委托单中得到配送信息，所述的配送信息包括：客户名称、客户需求的货物的总数量、总重量、总体积、卸货地址、要求的到货时间；(2)、从委运单得到的客户名称，从地址数据库中查询出客户的地址信息，包括客户的具体地址，客户间的距离；(3)、设定粒子群算法的参数，所述的参数包括种群规模、迭代次数，所述的种群规模表示初始配送方案的数量，迭代次数表示在众多的配送方案空间中的搜索次数；(4)、将上述的配送信息、客户的地址信息读入粒子群算法中；(5)、根据客户的数目，计算所需要的车辆数，对各个配送方案进行编码；(6)、使用解码算法进行解码；(7)、使用改进的廉价插入启发式算法(Cheapest Insert Algorithm)优化车辆内客户的顺序；(7.1)、建立改进的廉价插入启发式算法(Cheapest Insert Algorithm)模型，将客户u插入客户i和j之间的费用可以按照下面式子的定义计算：c1(i，u，j)＝diu+duj-dij (12)c2(i，u，j)＝bju-bj (13)c3＝Tu-T (14)c4(i，u，j)＝α1c1(i，u，j)+α2c2(i，u，j)+α3(i，u，j) (15)上式中，dij(i，j∈1，2…n)表示两个客户间的举例，bi(i∈1，2…n)表示在此客户的开始服务的时间，T表示线路总的等待时间；c1(i，u，j)表示插入u后，距离的增量；c2(i，u，j)表示插入u后，到达j客户的时间推迟量；c3表示插入u后，线路总的等待时间的增加量；c4(i，u，j)表示在客户i和j之间插入u的费用，是c1，c2，c3的加权和；(7.2)、如果所有的客户都已经分配给车辆，则算法停止；否则选择当前开始服务时间最晚的客户初始化一条线路。(7.2)、对于当前未分配的每个客户，将其插入当前线路中每个可行位置，按照(4)式计算插入费用，选取所有值中最小的值，将此客户插入相应的位置；(7.3)、重复第二步过程，直到此线路满足车辆的约束或者没有客户可以插入，则转第一步；(8)、根据配送成本计算方案，计算访问所有客户的线路长度或者时间或访问所有客户的费用，粒子的适应度定义为成本的倒数；(9)、比较粒子的适应度，找出种群中适应度最高的粒子保存，同时每个粒子和自身以前计算的适应度比较，保存自身最好的适应度；(10)、对粒子所代表的配送方案进行调整，根据如下的公式(16)进行粒子状态的更新：$\left\{\begin{array}{c}{\mathrm{Vi}}_{i+1}=c_1{\mathrm{Vi}}_t+c_2(P_{i,t}-{\mathrm{Xi}}_t)+c_3(P_{g,t}-{\mathrm{Xi}}_t)\\ {\mathrm{Xi}}_{t+1}={\mathrm{Xi}}_t+{\mathrm{Vi}}_{t+1}\end{array}\right.---\left(16\right)$ 上式中，Xi＝(xi1，xi2，…xiD)表示第i个粒子的状态，每个粒子表示D维空间的一个解，Vi＝(vi1，vi2，…viD)表示每个粒子的速度向量，且Vi满足：Vi≤最大速度Vmax；Pi表示每个粒子经历过的最优状态，Pg表示群体经历过的最优状态，c1是惯性权重，c2，c3是加速度常数；(11)、随机的选择一些粒子进行交叉操作，对各个粒子表示的配送方案进行调整；(12)、重复(6)～(11)，对可能的配送方案进行搜索，达到预定的迭代次数后，输出粒子群算法寻找到的配送方案。