指導(dǎo)老師林燦煌博士學(xué)生劉芳怡

1、指導(dǎo)老師：林燦煌指導(dǎo)老師：林燦煌 博士博士學(xué)生學(xué)生:劉芳怡劉芳怡Vehicle routing with time windows:Two optimization algorithmsMarshall L. Fisher ,Kurt O. Jornsten,Oli B. G. MadsenOperation Research,Vol.45,No3,May-June 1997,pp.488-492目的作者提出兩個(gè)最佳化方法來解決有時(shí)間窗限制的車輛排程問題。1. 拉氏鬆弛法(Lagrangian relaxation)。2. K-Tree鬆弛法(K-tree relaxation)。大綱介紹VR

2、PTW formulation拉氏鬆弛法(Lagrangian relaxation)K-Tree鬆弛法(K-tree relaxation)結(jié)論VRPTW之參數(shù) m=車輛數(shù) n=顧客數(shù);index 0=場站 Qk=第k輛車的容量 qi=顧客i的需求量 cij=從顧客i到顧客j的旅行成本 tij=從顧客i到顧客j的旅行時(shí)間 si=顧客i的服務(wù)時(shí)間 ei=顧客i的時(shí)窗下限 ui=顧客i的時(shí)窗上限 T=為一個(gè)很大的常數(shù)，所有路線之中具有最大的可服務(wù)時(shí)間 N=1,.,n，N0=N?0 M=1,.,mVRPTW之變數(shù) xijk= 1,代表顧客i至顧客j由第k輛車配送 0,otherwise yik 1

3、,代表顧客i被第k輛車拜訪 0,otherwise ti=顧客i到達(dá)時(shí)間 t0ek=第k輛車離開場站的時(shí)間 t0uk=第k輛車到達(dá)場站的時(shí)間VRPTW之?dāng)?shù)學(xué)模式 目標(biāo):求總旅行成本最小 00minNiNjMkijijxccij=從顧客i到顧客j的旅行成本xijk= 1,代表顧客i至顧客j由第k輛車配送 0,otherwisem=車輛數(shù),M=1,.,mn=顧客數(shù),N=1,.,n,N0=N?0 限制式(2): 表示車輛若服務(wù)某顧客，服務(wù)完之後必須離開該顧客。NiNjrjkirkxx0MkNr,xijk= 1,代表顧客i至顧客j由第k輛車配送 0,otherwisem=車輛數(shù),M=1,.,mn=顧客

4、數(shù),N=1,.,n,N0=N?0 限制式(3): 限制每部車的起點(diǎn)與終點(diǎn)皆來自於同一配送中心NiNjjkkixx100Mkxijk= 1,代表顧客i至顧客j由第k輛車配送 0,otherwisem=車輛數(shù),M=1,.,mn=顧客數(shù),N=1,.,n,N0=N?0 限制式(4): 計(jì)算車輛從這個(gè)顧客到下一個(gè)顧客點(diǎn)的到達(dá)時(shí)間，同時(shí)避免不必要的子迴路。 ti+si+tij-(1-xijk)TtjMkNji,xijk= 1,代表顧客i至顧客j由第k輛車配送 0,otherwisem=車輛數(shù),M=1,.,mn=顧客數(shù),N=1,.,n,N0=N?0ti=顧客i到達(dá)時(shí)間tj=顧客j到達(dá)時(shí)間tij=從顧客i到顧

5、客j的旅行時(shí)間si=顧客i的服務(wù)時(shí)間T=為一個(gè)很大的常數(shù)，所有路線之中具有最大的可服務(wù)時(shí)間 限制式(5): 計(jì)算車輛從場站出發(fā)到下一個(gè)顧客點(diǎn)的到達(dá)時(shí)間。 t0ek+t0j-(1-x0jk)Ttjx0jk= 1,代表場站至顧客j由第k輛車配送 0,otherwisem=車輛數(shù),M=1,.,mn=顧客數(shù),N=1,.,n,N0=N?0tj=顧客j到達(dá)時(shí)間t0j=從場站到顧客j的旅行時(shí)間t0ek=第k輛車離開場站的時(shí)間T=為一個(gè)很大的常數(shù)，所有路線之中具有最大的可服務(wù)時(shí)間MkNj, 限制式(6): 計(jì)算車輛從顧客i到場站的到達(dá)時(shí)間。 ti+si+tt0-(1-xi0k)Tt0ukxi0k= 1,代表顧

6、客i至場站由第k輛車配送 0,otherwisem=車輛數(shù),M=1,.,mn=顧客數(shù),N=1,.,n,N0=N?0ti=顧客i到達(dá)時(shí)間ti0=從顧客i到場站的旅行時(shí)間si=顧客i的服務(wù)時(shí)間T=為一個(gè)很大的常數(shù)，所有路線之中具有最大的可服務(wù)時(shí)間t0uk=第k輛車到達(dá)場站的時(shí)間MkNi, 限制式(7): 車輛抵達(dá)顧客i時(shí)，須在顧客i所規(guī)定的時(shí)間窗內(nèi)到達(dá)。 eiti uiNiti=顧客i到達(dá)時(shí)間ei=顧客i的時(shí)窗下限ui=顧客i的時(shí)窗上限 限制式(8): 場站的時(shí)間窗上下限 e0t0ek t0uk u0Mk Mk t0ek=第k輛車離開場站的時(shí)間t0uk=第k輛車到達(dá)場站的時(shí)間e0=場站的時(shí)窗下限u

7、0=場站的時(shí)窗上限 限制式(10): 每部車所服務(wù)的顧客總需求量必須小於等於車容量限制。 NiNjkijkiQxqMkxijk= 1,代表顧客i至顧客j由第k輛車配送 0,otherwisem=車輛數(shù),M=1,.,mn=顧客數(shù),N=1,.,n,N0=N?0qi=顧客i的需求量Qk=第k輛車的容量 限制式(11): 每一顧客點(diǎn)之到達(dá)時(shí)間必大於0 ti 0 限制式(12): xijk為0或1變數(shù) xijk0,10Ni MkNji,0 限制式(13): 確定每一顧客須被服務(wù)一次 限制式(14): yik 0,1 限制式(15): 任一車輛只能從任一顧客點(diǎn)離開一次Mkiky1Ni MkNi,0ikNj

8、ijkyxMkNi,0yik 1,代表顧客i被第k輛車拜訪 0,otherwiseSolution Methods作者於時(shí)窗限制的車輛排程問題發(fā)展兩種最佳化演算法:1. 拉氏鬆弛法(Lagrangian relaxation)。2. K-Tree鬆弛法(K-tree relaxation)。 方法1:使用Lagrangian relaxation來分割變數(shù)，目的是將一個(gè)問題分成好幾個(gè)子問題。 Lagrangian relaxation是一種可以求得近似最佳解（Near Optimal Solution）的方法，它藉由鬆弛(relax)複雜的限制式(constrain)，使得原始的問題(prim

9、al problem)簡化。它可以取代線性規(guī)劃(Linear Programming Relaxation)，因?yàn)槭象牫诜ㄋ蟪龅南陆?lower bound)比線性規(guī)劃所求出的下界，可以較逼近最佳化(optimal)。Solution Method- Lagrangian relaxation(1/7)在尋求目標(biāo)函的最小值時(shí)，可以將最複雜的限制式(constrain)移項(xiàng)再乘上一個(gè)Lagrangian multiplier，然後加回原的目標(biāo)函式，限制式為等式的情形下，氏乘必需為負(fù)的。使用次梯法(subgradient)，去找出氏乘，經(jīng)由斷地重覆計(jì)算以找到最接近最佳值的一個(gè)點(diǎn)。Solution

10、 Methods- Lagrangian relaxation(2/7) 將鬆弛限制式(15)並且導(dǎo)入拉式乘數(shù)ik。 子問題1變成: min- (16) subject to (13) and (14) 是一個(gè)半指派問題 ijikikySolution Methods- Lagrangian relaxation(3/7) 子問題2變成: min (17) subject to (2)-(12) 是一個(gè)最短路徑問題，含有時(shí)窗及載重限制(shortest path problem with time windows and capacity constraints,SPTWCC)。 由於SPTW

11、CC可能包含負(fù)cycles，為了避免發(fā)生此情形，two-cycle elimination(Kolen et al.1987)被使用來解決此種情形。ijijkikijxc)(Solution Methods- Lagrangian relaxation(4/7) 為了協(xié)調(diào)鬆弛限制式(15)所帶來的問題，將之寫成對偶型式: (18) Where)(max)(*ww)1(,nmR ijkikjikijkikijkijyxxcw)(min)(Solution Methods- Lagrangian relaxation(5/7) 由於x，y在原始與對偶問題的目標(biāo)函數(shù)的最佳解可能會有一個(gè)缺口(Gap=

12、(Optimal solution-Lower bound)/Lower bound in %)。在這個(gè)case 對於VRPTW問題將是一個(gè)lower bound。 在式子(18)使用梯度最佳解(subgradient optimization)來做迭代。作者為了關(guān)閉對偶缺口，藉由引入branch-and-bound method，接著使用變數(shù)分離法(Variable Splitting Approach)去判斷l(xiāng)ower bounds。)(*wSolution Methods- Lagrangian relaxation(6/7) 下面分割的規(guī)則是被使用在branching process:

13、(1)分派一輛車給顧客，如固定yik不是1就是0。(2)選擇過去最常拜訪的顧客。Solution Methods- Lagrangian relaxation(7/7)Solution Method - K-tree Approach(1/3) Tree:Basis: one node is a tree K-tree:Basis: 有K個(gè)children is a K-treeSolution Method - K-tree Approach(2/3) Example: 4-tree00001234567891011*1112131415Solution Method - K-tree Approach(3/3) 方法2:利用K-tree鬆弛法，是於時(shí)窗限制下所發(fā)展出的K-tree演算法;此法為應(yīng)用求解TSP中典型解法1-tree的延伸。 在此法中，須假設(shè)每一路徑中至少須有兩