《物流配送车辆优化调度理论与方法》9车辆优化调度算法的计算机实现

1、物流配送车辆优化鲫度理论与方法第九章车辆优化调度鼻法的计算机实现 183 第九章车辆优化调度算法的计算机实现物流配送的日常调度作业工作量很大，尤其是在运输条件比较夏杂.拥有运输车辆 数较多的情况F,单纯采用人工办法在规定时间内连续确定配送车辆整体调度的每日最 优方案更是不可能的,而利用计算机,建立物流配送车辆优化谢度系统,因箕具有对大 信数据资料进行快速综合加工处理的功能，则可以然助实现配送工作的“实时优化管 理,建立物流配送车辆优化调度系统，就需对车辆优化调度算法计算机实现。本章讨 论与之相关的数据处理及算法的实现过程。9.1 系统基础数据9.1.1 系统蓦础数据内容车辆调度优化系统投入使用

2、基础数据是必不可少的，基咄数据包括动态数据与傍态 数据两部分。1 .静态数据指运输业务范围内相对稳定的数据，如：道路网络数据、车场驻地和常用送货点位 置数据、车辆数据及司机数据，这类数据只需在计算机系统实随初期一次输入以后按需 调人，也可随时更新，以避免每次重复瑜入数据D具体而言，包括：道路网络数据：包含道路的物理属性,如一般道路、桥梁等；道路的性质属性, 如道路等级、速度限制、通行车辆种类等；以及道路的行驶属性，如单行道内行道、 临时禁止通行等数据。车场驻地和常用送货点位段数挣：包含它tn的位置数据及相关的属性数据,如 编号、名称、所在街道名称、负款人、电话号码、传真及备注等数据。.车辆、司

3、机数据：包括车辆、司机的自身属性数据及车辆、司机的限制、约束 驾驶的条件以及运作成本等数据。2 .动态数据指运输业务范:围内经常变化的数据，包含送货点的需求数据.它详细说明了客户对第九车辆优化调度算法的计算机实现 185 发送货物的各项要求、当日车班数据、当日送货点分布等数据。如：用户对送货地点、货物品种、数量、货物装卸等的要求。对有时间窗限制的多车车 辆调度问题还包括任务开始时间窗和服务时间要求。9.1.2 系统主要基础数据结构在讨论了基础数据的内容基础之上，进一步设计基础数据结构，好的数据结构是提 高算法效率的前提,而基砒数据结构设计中尤为重要的是道路网络数据结构和送货点信 息结构设计。1

4、 .道路网络数据结构采用“瓠段集合（Arc）” + “节点集合（Nxfe）”数据结构来表达，如图9-1所示：75-ArcdD132231312367433.工5，一865NetWork-Arc-list2 Node Number Arc-ID 取向遢道ArcllabAMN“，Ntn101211322441654 . 891Network-Node-listArc*IDRoad-NumRoad-TypeLengthSp”dLtadt1交大路15400702沙樽第i620060 5通锦桥路1340060道路网络结构在实际应用中是繁琐的，在系统中采用一种简洁易行的数据结构，从 弧段即节点数据库(事先

5、建好库,结构如上图表示)中读取道路网络数据，在顶点已编 号的情况下，建立NetWak - An: List和NrfW<ik Nxfc Index两个结构体数组以及对Net- Work-AnrList进行排序，这两个数组：一个用来存储和孤段相关的数据(NeiWH-ArvLasi).另一个则存储和节点相关的数据(NrtWark-Nxle Index)。NecWatk-ArcList用一个结构体数组维护并且以弧段起点的点号来顺序排列.同一 起点的弧段可以任意排序°这个数组类似于邻接矩阵的压缩存储方式，其内容则具有邻 接多重表的特点，即一条边以两顶点表示。NetWork-Nxlc In

6、da则相当于一个记录了顶点出度的索引发.通过它可以很容易地 得到此顶点的出度、与它相连的第一条弧段在弧段数组中的位置、此顶点相关的最大边 数及节点的属性数据。此外，道路的属性数据作为道路网络不可少的一部分也是必须记录的.如果是存放 在数据文件或数据库中的话，在进行亍算前则需把数据依要求读进来。这样，计算车辆 调度优化所需的道路网络信息已经完备。2 .车场驻地和常用送货点位置数据车场驻地和常用送货点位置数据-定要确保与道路网络数据建立起关联，可以通过 地理坐标或惟一字段,如道路名称，节点班号等与道路网络数据建立关联。3 .送优点需求数据包括用户对送货她点、货物品种、数量、货物装卸等的要求。针对有

7、时间窗限制的 车辆网度问题还包括任务开始时间窗、任务服务时间等要求，可表示为如下二维形式, 如表9-1：表9-1送货点需求信息表12345678序 号送货地 点位置运*需要车 到送货任务 时间位约束联务 时间所送货物 品并、最早时间般费时间 186 物泣配送车机优化调度理论与方法9.1.3 系统甚本敷掘管理流程网拿侑g)。卬筝帐及m，*入图9-2系统葛本效掘管理流程图.W*ffl人LED2 |用机信图9-3系统业务流程图9.1.4 系统业务流程图系统业务流程图如图9-3所示：首先由用户传来需求数据，调度部门根据司机和 车辆情况，依据道路网络数据,生成调度方案，最后将调度方案送给司机和仓库部门。

8、第九章车辆优化调度算法的计算机实现1879.2 系统算法实例将车辆调度优化理论算法直接应月于货运组织的日常调度作业还有一定距离，如何 将算法转变为计算机程序，还需一个设计过程，在此介绍解决有硬时间窗约束的通车场 单车型车辆调度同胸的计算机实现步募，以飨读者。9.2.1 有时间窗妁束的单车场单车型调度问题描述以s,表示任务i的开始时间，任务i处需要耽搁的时间(卸货)为工(即服务时 问).设开始时间需在一定的时间他用El；, Er.l内，其中EI；为任务i的允许最F开 始时间.L1为任务i的允许最迟开始时间.则有皿&、45。如果车辆达到i的时间 早于ET,则车辆需在i处等待；如果交辆达到时

9、间晚于ET,则任务i要延迟进行。9.2.2 C-WJT 法步骤依据CW算法原理，求解步骤如下：(1)计算 S (i, D,令乂= | S (i, j) Is (i, j) >0|；(2)在M内按s (i. j)从大到小的顺序排列；(3)若M=6,则终止,否则对M内第一项s (i. j)考察对应的(i, i),若满足下 述条件之一：若点i和点j均不在已构成的线路上；若点i或点j位于已构成的线路匕 但不是线路的内点；若点i和点j位于已构成的不同线路上,均不是内点，旦一个是起点，一个是终 点，则转下步，否则转(7),9.2.3 点i和点jil接后的总货运量Q,若心可(。乙a&l为装车复杂系数，q 为车的容显)，为转下步,否则转(7);(5)计算 EFjMS+W + q-Sj若9=0,则转(6);若叫<0时，则计算当-EF/5，则转(6),否则转 (7);若%>0时,则计算'二”/3,当田乙考，则转(6),否则转 (7);(6)连接点点i和j.转