人工智能与专家系统学期论文班级：06管理信息系统姓名：周健学号：20062905日期：2006年6月蚁群算法在物流配送车辆调度中的应用一物流配送车辆调度问题概述物流运输是现代化物流系统的一个重要环节，它是指按用户的订货要求，在物流中心进行集货、送货，并将货物及时送交收货人的活动。
如有一个中心货场，需向几个车辆调度运送货物，每个车辆调度对货物有一定的需求，运送货物的车辆在货场装满货后发出，把货送到各车辆调度处，完成任务后返回货场，如何满足用户需求的费用最小的车辆行驶路线，即送货车辆优化调度。
又如，若干厂家生产一些产品，需要运到中心仓库，车辆从仓库出发，到各厂家去装货，装满后返回仓库，在满足厂家发货要求的清况下，按什么路线行驶，可使总费用最少，即集货车辆优化调度。
这两个问题实质是相同的，只是装货任务或卸货任务不一样。
在货物量较少的情况下，用一辆车完成一项任务时，车辆不能满载，这样，车辆的利用率最低，因此可考虑用一辆车完成多项任务。
图1表示了3条车辆行驶线路〔图中矩形表示物流中心，圆圈表示货物运输任务〕集货或送货非满载车辆调度问题一般描述为：有一个车场，拥有一定数量容量为q的车辆，现在有l项货物运输任务需要完成，以1,,l表示，已知任务i的货运量为gi(i=1,…,l),且gi<=q，求满足货运需求的费用最小的车辆行驶线路。
1车辆调度问题相关算法对于集货或送货的车辆调度问题，解决的方法大致分为下面几类。
a先安排线路后分组的方法：这种方法首先构造一条或几条很长的线路（通常不可行），它包括了所有需求对象，然后再把这些很长的线路划分为一些短而可行的线路。
具体进行时，一般是先解一个经过所有点的旅行商问题，形成一条线路，然后根据一定的约束（如车辆容量等）对它进行分化。
b.先分组后安排线路的方法：这种方法先把节点和（或）弧的需求进行分组或划群，然后对每一组设计一条经济的线路。
其目的在于形成需求点的径向区域，从车场发出的射线“扫过”这个区域，使不超过车辆容量的需求点组成一个区域，一个区域就是一个组，当形成一系列这样的组后，再对每一组的各点安排线路。
c.节约/插入算法：根据一定的准则（如节约准则），把不同线路上的点插入线路，直到所有点都被安排进线路。
d.改进/交换法：在初始保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以替代原来的解，使目标函数得以改进，一直继续到不能再改进为止。
e.基于数学规划的算法把问题直接描述为一个数学规划问题，根据其模型的特殊构形，应用一定的技术（如分解）进行分化，进而求解已被广泛研究过的子问题。
2车辆调度问题数学模型（1）一般车辆调度问题模型为构造数学模型方便，将车场编号为0，任务编号为1,,l，任务及车辆均以点i(i=0,1,,l)来表示[45]。
定义变量如下：模型中，gi表示任务i的货运量，cij表示从点i到点j的运输成本，它的含义可以是距离、费用、时间等，一般根据实际情况确定，可同时考虑车辆数和运行费用，如下确定：1)当i为车场时，包括固定费用和运行费用2)当i为任务点时，只有运行费用，即其中，C1为相对于运行时间的费用系数；C2为车辆的固定费用，即增加一辆车的边际费用。
一般认为，派出一辆车的固定费用远远高于车辆行驶费用，因此该模型是在绩效化车辆数的前提下，再极小化运行费用。
减小C0的值将会使使用的车辆数增多，而线路长度缩短。
若令C1=0,C0>0，则模型目标是使用的车辆数最少。
（2）有时间窗车辆调度问题模型在一般车辆调度问题基础上加入时间窗约束，即各个任务均有一个时间窗。
设完成任务i需要的时间表示为Ti，任务i的开始时间需在一个范围【ETi，LTi】内，其中ETi为任务i的允许最早开始时间，LTi为任务i的允许最迟开始时间。
如果车辆到达i的时间早于ETi，则车辆需在i等待，直到ETi才能开始服务；如果车辆到达时间晚于LTi，任务i要延迟进行，求满足货运要求的费用最少的车辆行驶线路，此问题称之为有时间窗的车辆调度问题。
以s i表示车辆到达任务i的时刻，ti表示车辆在任务i的等待时间，t ij表示车辆由任务i行驶到任务j的时间，一般有以下关系式：(3) 时间窗时间窗分为硬时间窗和软时间窗。
硬时间窗是指每项任务必须在要求的时间范围内完成，即必须满足第三式，若超出这个时间范围，则得到的解为不可行解。
软时间窗指如果某项任务不能在要求的时间范围内完成，则给予一定的惩罚。
若车辆在ETj之前到达任务j，则车辆在此等待，发生了机会成本损失，此时t i>0；若车辆在LTj之后到达任务j，则任务被延迟，需支付一定的罚金。
在本文中，我们主要研究硬时间窗车辆调度问题。
二车辆调度问题的蚁群算法1 一般车辆调度问题的蚁群算法我们用一赋权有向图G=(V,A,d)来表示配送路径问题，其中V={v0,v1,v2…vn}为一系列点的集合。
v0用来表示配送中心，vi(i=1,2…,n)表示各任务，为一系列弧的集合，dij与弧(vi,vj)相对应，表示vi到vj的距离，对于任务vi给定了需求量qi（其中q0=0），寻找最短路径，当然，使用的车辆也应尽可能少。
同时满足以下条件和假设：a.所有的配送车辆以配送中心为起点并最终回到配送中心。
b.每条配送路径上各需求点的需求量之和不超过车辆的载重量。
c.每个需求点的需求由且仅由一辆车一次送货满足。
我们用人工蚂蚁替代车辆来服务任务点，当下一个要服务的任务点会使运载总量超出汽车载重量，就返回到配送中心，表示这辆车完成此次运输，该辆车接着出发服务其余任务，直到所有任务点都得到了一次服务，此时代表该车的蚂蚁完成一次巡游。
当所有蚂蚁都巡游一次，记为一次循环。
一次循环后，根据各蚂蚁巡游历程的好坏(目标函数值)，计算信息素增量，更新相关路径上的信息素。
在这里，我们应用第四章介绍的自适应改进蚁群算法来解决物流车辆调度问题。
算法具体步骤如下：（1）初始化，设置各路径初始信息素；（2）将每只人工蚂蚁设置起点为配送中心；（3）求转移概率p(i,j),通过轮盘赌方法得到i的下一个点j；（4）计算i和j连线后线路上的总货运辆sum_g,若sum_g≤q（q为车辆最大容量），把点i放入禁忌表中，计算点i到点j的路径长度和费用，转（3）；否则，转（5）;（5）统计车辆数，sum_g置0，计算路径长度，转（3）；（6）计算各边信息素增量，更新信息素；（7）若算法循环NCmax则停止，计算最短路径长度，输出最短路径及最少费用，否则转（2）。
2有时间窗车辆调度问题的蚁群算法有时间窗的车辆调度问题是一个复杂的非线性组合优化问题，目前，对它的研究多以确定的车辆数目来求解，对不确定的车辆数的问题涉及较少，本文用蚁群算法对求解车辆数不确定的有时间窗车辆调度问题进行了研究，设计动态确定车辆数和随机搜索路径的新方法，使蚁群算法在计算过程中能自动寻找满足要求的最少车辆数，并实现车辆数和路径长度的同时优化，相关设定如下：（1）初始时，当车辆从车场0开往任务i时，若ETi ≤t0i≤LTi，取si =t0i,若t0i<ETi;取si=ETi;（2）t ij=dij/v，其中v为车辆行驶的速度；（3）若把各点的距离作为费用时，cij =dij；（4）当车辆到达下一个j时，sj =si+Ti+tij我们考虑硬时间窗约束车辆调度问题，即前第三式必须满足。
用人工蚂蚁代替车辆来任务点当下一个要服务的点使运载总量不超出汽车载重量，并且车辆到达该点的时间在时间窗范围内，车辆继续开往下一个任务点。
否则，只要违反其中一个约束，车辆返回车场0，进行相关初始化以后从车场0出发继续服务其余，直到所有任务都得到了一次服务，此时该蚂蚁完成一次巡游。
当所有蚂蚁都巡游一次，记为一次循环。
一次循环后，根据各蚂蚁寻优历程的好坏（目标函数值），计算信息素增量，更新相关路径上的信息素。
算法步骤与一般车辆调度问题只在（4）有变化，具体步骤见上文。
三仿真实验1一般车辆调度问题蚁群算法实验1：例子是这样的：某物流中心有4台配送车辆，车辆的最大载重量为1t，需要向7个客户送货，物流中心用0表示，7个客户和物流中心的坐标及货物需求量见表1表1 实验1的坐标数据及需求信息相关参数设置：取蚂蚁数sum_ant=10，最大循环次数Nc=10，α=1，β=2，ρ=0.7，Pbest=0.05，算法运行50次求平均。
在50次算法运行中，每次都找到了最优路径距离217.8135，而且每次都只用较少的代数就能找到最优路径。
最优路径为：0-1-0-6-7-0-2-3-4-5-0，所用车辆为3辆。
最优路径见图1图1 蚁群算法所得最优配送路径图表2 各种算法结果对比表实验结果与例子算法的比较见上表2，表中所用时间为50次平均所得结果。
从实验结果我们看到，AMMAS在搜索成功率和所用时间上都是最优的，证明了它的有效性。
当然，我们必须指出，由于这个实验涉及的任务点较少，所用蚂蚁数也较少，这使得AMMAS时间复杂度较小；当问题规模增大时，AMMAS 的搜索时间将有较大增长。
实验2：某物流中心有5台配送车辆，车辆的最大载重量为8t,需要向20个客户送货。
物流中心的坐标为（14.5km,13.0km）,20个客户的坐标及其货物需求量见表3。
表3 实验2的坐标数据和需求信息相关参数设置：取蚂蚁数sum_ant=20，最大循环次数Nc=2000，α=1，β=2，ρ=0.7，P best=0.05，算法运行10次求平均，实验结果见表4：表4 实验结果统计表图2 蚁群算法所得最优配送路径图2 时间窗车辆调度蚁群算法实验3：有8个分店和1个配送中心，各分店的需求量为q（ii=1,2,,8）（t），装货（卸货）时间Ti（h）以及分店要求的服务时间范围[ai ,bi]由表5给出。
货车的载重量均为8t，车速为50km/h,单位运输成本为1元/km，配送中心（其编号为0）与8个客户之间及8个客户相互之间的距离d(i,j=1,2,,8) ij见表6。
要求合理安排车辆配送路线，使配送总路程最短。
表5 任务的特征及需求表6 客户间及客户与配送中心的距离相关参数设置：取蚂蚁数sum_ant=16，最大循环次数Nc=500，α=1，β=2，ρ=0.7，Pbest=0.05，算法运行10次求平均，实验结果见表7表7 实验3结果统计表本文蚁群算法找到的最优路径为910km，最优行驶路径为0-6-4-3-0-1-2-0-8-5-7-0，在10次运行中有7次找到了最优解，所用的车辆数均为3。
AMMAS所得结果和其他算法的比较见表8从表我们可以看到，AMMAS在搜索成功率和搜索时间上较其他两种算法均有明显优势，说明了它的有效性。
表8 实验结果比较表.四总节物流配送车辆调度是个NP难题，求解往往比较复杂。
