资源描述：
《货运汽车调度的一种启发式算法_郭耀煌》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第7卷第1期(总第29期)系统工程1989年1月47货运汽车调度的一种启发式算法郭耀煌范莉莉【提要】本文就减少城市货运卡车的空驶里程提出了一种启发式井法和与之。相适应的派车方法一、引言,,大中型城市的道路网十分复杂每天的货运量又非常大采用人工调度常造成很多不必,,。要的空驶这不仅浪费大量人力物力也加剧了城市交通拥挤和环境污染根据某市汽车运,1%,输公司的概略统计如提高实载率(重车行驶里程与总行驶里程之比)一年内即可减少,。运输成本一百万元左右节约汽油70万升对于担负大中型城市货运任务的汽车运输公司来,,,。说如何科学
2、地进行车辆调度提高其实载率具有十分重大的经济意义,。,为有效提高货运卡车的实载率必须拟定出准确可靠的计算方法一般说来运输公司,。,在每天下午或晚上才能最后确定第二天的货运任务然后安排行车路线因时间紧迫要求,,。;计算速度要快此外为能适应天天变化着的不同条件还要求算法有较大的灵活性、、,,。现有的一些算法1[〕〔2〕〔”〕难于全面满足上述要求为此本文提出了一种新算法,,,,。这种算法精确度高计算速度快所需存贮量少适于多个车场可在微型机上实现由于,它能在很短时间内打印出计算结果和行车路线(包括车辆的运行路观和要完成的任务
3、每条,,,行车路线的空驶里程和实载率所需车辆数等)对计算机要求不高这就特别适于我国城。市汽车运输公司目前使用,我们将此算法算出的结果与某市第二汽车运输公司过去若干天的调度计划(人工调度)进,8,。行了事后对比发现可提高实载率%一10%派车数量也有所减少二、数学模型,。假定有一运输公司承担某市各客户委托的货运任务设已核实第二天的货运任务共有:、2、、。、、·、。:,g:92s。,项A月……A其货运量分别为一根据运输工具的载重量和车箱,a:、a:、、a二。,容量(假定车型相同)易将其折算成需要的车数……此外假定该运输公司
4、本。:,,.文于1988年6月25日收到郭规煌西南交通大学杆理工程系系统工权与运筹学教研室主任刑教授范莉莉酉,,南交通大学管理工程系教师硕士n。;,、。、2、、。,.,可使用个车场AA……A它们和m项货运任务的发货点和收货点都处于同_。二,,、。、2、、.+,,一个连通的道路网L各车场可提供的车辆数分别为bb……b可接收的回程车,。;:、,。;2、、`。;:。数分别为bb……b,从某一发货点将货物运抵收货点卸车之后的空车应转向哪一个发货点去继续执行运输,,任务(或回车场)呢?由于这种转移是在车辆空驶的条件下完成的因而
5、应使这种转移的。,,不存在空总妞越小越好另一方面将货物由指定发货点运到指定收货点全为重车行驶,,驶故在研究使总空驶里程最小这一问题时可将侮项重载运输任务视为一收缩点4F]或策载,`二1,,,。点每个收缩点A(i2……nt)所需的空车数山就等于它能提供的空车数i发往点j的空车数为为,,:设由点则可写出该问题(称为问题T)的数学模型如下用十口用+月s=i“`,x`,万叫刃尸t刃刃科刃川刃耐户卜戈52=as,才“1,,,2……m·`·`z=az-二1,,,x2…m(1)戈`,`,=阴+l,,n+2……,川+n,(bi劣`I
6、`,,=。+1,m+2,,m+n(bj……劣`J,,=,,m+n》0且为整数ijl2……,,在式(1)中由空车发点`到空车收点j的距离ic,.可按点i之收货点至点j之发货点间的最短,,c“。路确定5[〕其中为由第i项运输任务的收货点返回其发货点的最短距离、:运输问题T的运输表可分为四个区域收缩点收缩点(A区)收缩点车场尹、—,。—(AB区)车场收缩点(AB区)以及车场车场(B区)请参见表1——表1收空车收缩点车场发车数··,··4。,1二,。,:发空车A二月。A月’z…A,·月:…一耘蛛拓月A.…Q才收绷点一车场一一
7、月A了J“,,(AB,)’x,0zù一XìB一(月B)一点.··,,,.,收车数aJ02……口.b,二护f…b,为加快不!·算速度,减少计算机内存,以满足运输公司裔尽快得到调度方案的要求,我们。特设计了下述启发式算法三、启发式算法,只考,。:现先不考虑车场虑收缩点问的空车调运问题并称此问题为问题Tns。二c`zx`smi刃刃,,一11lT。(2)a`,=,,,川刃为=ji12……义*,二a,,=1,2,,;,:万j……二`j,,=1,,,。:>0几为整数ij2……,,。显然这是一个一般的产销平衡运输问题很容易用表上作
8、业法求解设求出的最优解`。’,,x则以这个解中的非零变量值作为问题T解的对应非零变量值这样褂到的解对问题T是。,`也是可行的可是山于这时没有和车场对应的非零变量(在丧1的刀B区和月B区中没有,。非零变最)故无法以此解为纂础拟定派车计划为能给,`“’出满意的派车计划我们对土面得到的局部(对问题T来说)最优解X用下述。启发式算法逐步进行调整x`。’
