基于遗传算法的多车型动态车辆调度问题研究
目录
基于遗传算法的多车型动态车辆调度问题研究 .......................................................................... 1
1.总体概述——车辆调度优化的意义 .............................................................................................. 1
2.多车型车队动态调度优化问题模型 .............................................................................................. 2
(1) 模型概述 ................................................................................................................................... 2
(2) 问题约定 ................................................................................................................................... 2
(3) 变量说明 ................................................................................................................................... 3
(4) 模型建立 ................................................................................................................................... 7
3.模型的遗传算法设计 ..................................................................................................................... 8
(1) 编码方案 ................................................................................................................................... 8
(2) 适应度函数 ............................................................................................................................... 9
(3) 遗传操作 ................................................................................................................................... 9
(4) 车辆调度方案的生成 ............................................................................................................. 11
1.总体概述——车辆调度优化的意义
在我国有一半的物流成本消耗在货物运输环节上，所以运输合理化在很大程度上影响着物流效益。在物流业务活动过程中，直接耗费的活劳动和物化劳动所支付的费用主要包括运输费、保管费、包装费、装卸搬运费、运输损耗等，其中运输费用所占比重最大，是影响物流效益的一项主要因素。货运车辆是货物运输的直接载体，同时也是货物运输作业过程中最重要的可支配资源。据统计，我国货运车辆的平均实载率为60.375%，载重利用率是110.25%，里程利用率为54.76%，全国载货车辆空载率高达47.9%，即有近一半的行程相当于空车运行。每年我国空载车辆造成的燃油、车辆和道路损耗以及劳动力浪费大约3000亿元，浪费极为严重。由于货物运输在整个物流系统中的重要作用，使得对货物运输作业进行优化组织成为降低物流成本、提高物流效率的重要手段和关键。货物运输的优化组织其目的就是运用所掌握的各种资源合理安排运输任务，消除对流、迂回、重复等不合理现象，从而以最少的资源消耗来完成最多的运输任务。在庞大的运输网络中，为了最大限度地满足在不同时段不同地域上所产生的运输任务需求，并达到以最少的资源投入获得最优经济效益的目的，需要对所掌握的数量有限的货运车辆资源进行有效管理，提高车辆利用率，制定出合理的车辆调配方案，这也正是铁路、公路、水运、航空等运输部门和各大物流企业在实际工作当中所直接面对且函待解决的难题。
本案例中河北快运集团主要从事或货运和快运，这两项业务都需要大量的车辆运输，在实际运作中运输成本肯定会占企业总成本的很大一部分。而且从案例中和河北快运的网站中了解到河北快运并没有发挥它的网络优势，没有对车辆进行合理调度，也存在着很大的浪费。所以需要对有限的车对资源进行合理调配，尽可能的降低车辆的空载等浪费，从而降低企业运营成本，增强企业的市场竞争力。
2.多车型车队动态调度优化问题模型
(1) 模型概述
由于河北快运集团从事货运的车辆有多种型号，小型厢式货车、厢式货车、重型厢式货车等五种车型，在实际运输中，不同的任务量、不同的业务应选择不同的车辆，所以河北快运集团车辆的调配是多车型的有限制的车辆调配。
在实际的运输中，一般都将服务周期划分为若干个时段，在每个时段内运输网络的各节点处都可能产生运输任务。任务一旦出现，就需要已经分配到任务所在地的车辆来完成该任务，即进行车队调度。所以车队调度要完成两方面的工作，时间上的和空间上的。首先要制定出时间上的任务发运计划，即为各项运输任务指定发运时间，其次又要完成空间上的车辆分配，即为各项任务指定运输车辆。从而车队动态调度优化就是指在服务周期内，通过制定和优化任务发运计划，并按照一定原则科学地调度车辆。同时要达到对车辆的统筹调度，在进行某时段的车辆调度工作时不仅要考虑本时段的运输成本，还要考虑对未来各时段的车辆调度工作的影响，应该追求整个服务周期内运输总成本最低,而不是单时段的成本最低。
(2) 问题约定
①运输网络：由各个任务节点以及各个节点之间的路径组成，网络中的任务、车辆的数量和状态随着时间的推进发生变化。
②任务节点：实际运输时的运作模式都是点对点的直达运输模式，所以将公司营业网点都抽象成任务节点。
③服务周期：规定的一段调度执行时间，按一定的时间长度将其分成若干个单位时段，每个时段内每个任务节点都可能产生运输任务。
④产生的任务类型：车队要承载的任务均为不同类型。
⑤任务时间窗情况：由于在任务发运前，要制定任务发运计划，所以每个任务都有确定的起运时间。并且所使用的车型统一，因此根据任务运输的距离，到达时间也是一定的，由此可知任务时间窗为硬时间窗。同时约定不会出现当超出任务允许的时间范围时任务消失的情况。要求每个运输任务都能及时地得到满足。
⑥任务分布情况：在第一个任务产生时段，运输任务分布已知。其他时段的任务情况未知。
⑦两地间所需的运输时间：由两地间的实际距离与承载任务的车辆的车速决定，但为了研究问题方便，两地间的运输时间约取整数倍时段数。
⑧车辆型号：根据不同类型的任务的需要，车辆拥有不同型号。
⑨车辆和任务匹配情况：所有同一类型的车辆可以完成需要这种车型的任一个任务，并且满足一辆车一次只能完成一个任务，其中规定任务类型与车型一一对应，即车型为k的车辆可承接任务类型为k的任务。
⑩关于不同车型的车辆的费用的约定：不同车型的车辆的载重量、体积、时速、固定成本、吨公里油耗、养路费、轻质费率均不相同。
(3) 变量说明
①基本变量
运输网络变量G(V,E)：运输网络结构变量，其中V表示中的节点集合，N表示节点的个数，为大于等于1的整数。E表示G中路径的集合。如图一所示：
②调度变量
服务周期C：按一定时间长度划分为P个时段，从而有C={1,2…p}，其中p为大于等于1的正整数。
任务计划长度：一次制定的任务发运计划包括几个时段，，且为，且为整数变量。
K：特定一种任务类型或车型的编号，其中k为大于等于1的整数。
：运输网络中存在的任务类型或车型数目。为大于等于1的整数。
：运输网络中存在的车辆数目。
：t时段存在的总的任务集合。其中，表示t时段，第i个任务的任务集合，表示第t时段，第i个任务点，类型编号为k的任务集合，i=1，2，…N。
：t时段总的任务数，其中为大于等于0的整数。
：t时段，第k种类型的任务集合。其中，表示在t时段，第i个任务点，第k种类型的任务集合，i=1，2，…N。
：t时段安排发运并要在t时段起运的任务数，其中为大于等于0的整数。
：t时段安排发运并要求在t时段起运的第k种类型的任务集合。其中，表示t时段，第i个任务点安排发运并要求在t时段起运的第k种类型的任务集合，i=1，2，…N。
：：t时段安排发运并要求在t时段起运的第k种类型的任务数。为大于等于0的整数。
m：第k种类型的某一个运输任务，。
ts()：运输任务m的时额间窗,。
：运输任务m的起运时间,也是运输任务m的左时间窗,则有。
：运输任务m的要求到达时间,也是运输任务m的右时间窗,则有。
：t时段可调度的总的的车辆集合。其中，表示t时段，第i任务点可调度的车辆集合，，表示t时段，第i个任务点，第k种车型可调度的车辆集合，i=1，2，…N。
：t时段可调度的总的车辆数,其中为大于等于1的正整数。
：t时段可调度的第k种类型的车辆集合。其中，表示t时段，第i个任务点处，第k种类型可调度的车辆集合，i=1，2，…N。 ：t时段可调度的第k种类型的车辆数，其中为大于等于1的正整数。
：t时段有运输任务承接，并要在t时段起运的第k种类型的车辆集合。其中，表示 t时段在第i个任务点有运输任务承接，并要在t时段起运的第k种类型的车辆集合，i=1，2，…N。
：t时段可调度的第k种类型的车辆数，其中为大于等于1的正整数。
：t时段有任务承接，并要求在t时段起运的第k种类型的车辆集合。其中，表示t时段在第i个任务点有任务承接，并要求在t时段起运的第k种类型的车辆集合，i=1，2，…N。
：t时段有任务承接，并要求在t时段起运的第k种类型的车辆数，其中为大于等于1的正整数。
：t时段需要空车移动到另一任务点的第k种类型的车辆集合。其中，表示 t时段在第i个任务点需要空车移动到另一任务点的第k种类型的车辆集合，i=1，2，…N。
：t时段需要空车调配到另一任务点的车辆数，其中为大于等于1的正整数。
：t时段需要原地等待到下一时段的车辆集合。其中,表示t时段在第i个任务点需要等待到下一时段的第k种类型的车辆集合，i=1，2，…N。
：t时段需要原地等待到下一时段的车辆数，其中为大于等于1的正整数。
：承接编号为m，类型编号为k的运输任务所需的费用，其中。