六、運(yùn)輸及配送路線的優(yōu)化

1、六、運(yùn)輸決策及配送路線的優(yōu)化六、運(yùn)輸決策及配送路線的優(yōu)化6.1運(yùn)輸系統(tǒng)的重要性與功能運(yùn)輸系統(tǒng)的重要性與功能6.2基本運(yùn)輸方式及其運(yùn)營(yíng)特點(diǎn)基本運(yùn)輸方式及其運(yùn)營(yíng)特點(diǎn)6.3運(yùn)輸合理化運(yùn)輸合理化6.4運(yùn)輸路線的選擇運(yùn)輸路線的選擇6.5車輛路線、時(shí)間安排車輛路線、時(shí)間安排6.1運(yùn)輸系統(tǒng)的重要性與功能運(yùn)輸系統(tǒng)的重要性與功能q運(yùn)輸運(yùn)輸指借助公共運(yùn)輸線及其設(shè)施和運(yùn)輸工具來實(shí)現(xiàn)人指借助公共運(yùn)輸線及其設(shè)施和運(yùn)輸工具來實(shí)現(xiàn)人與物空間位移的一種經(jīng)濟(jì)活動(dòng)和社會(huì)活動(dòng)。與物空間位移的一種經(jīng)濟(jì)活動(dòng)和社會(huì)活動(dòng)。q交通交通與運(yùn)輸反映的同一過程的兩個(gè)方面。與運(yùn)輸反映的同一過程的兩個(gè)方面。v 同一過程：運(yùn)輸工具在運(yùn)輸網(wǎng)路上的流動(dòng)；同

2、一過程：運(yùn)輸工具在運(yùn)輸網(wǎng)路上的流動(dòng)；v 兩個(gè)方面：兩個(gè)方面：v 交通關(guān)心的是運(yùn)輸工具的流動(dòng)情況交通關(guān)心的是運(yùn)輸工具的流動(dòng)情況(流量的大小、擁擠的程度流量的大小、擁擠的程度)v 運(yùn)輸關(guān)心的是流動(dòng)中的運(yùn)輸工具上的載運(yùn)情況運(yùn)輸關(guān)心的是流動(dòng)中的運(yùn)輸工具上的載運(yùn)情況(載人與物的有無與載人與物的有無與多少，將其輸送了多遠(yuǎn)的距離多少，將其輸送了多遠(yuǎn)的距離) v 運(yùn)輸是交通的目的運(yùn)輸是交通的目的q運(yùn)輸系統(tǒng)的重要性運(yùn)輸系統(tǒng)的重要性v 地域分工專業(yè)化地域分工專業(yè)化v 規(guī)模經(jīng)濟(jì)規(guī)模經(jīng)濟(jì)v 競(jìng)爭(zhēng)加劇競(jìng)爭(zhēng)加劇v 土地價(jià)值的提高土地價(jià)值的提高q交通運(yùn)輸系統(tǒng)的構(gòu)成要素：v（1）運(yùn)載工具（2）通路（3）場(chǎng)站（4）動(dòng)力（5）通

3、信（6）經(jīng)營(yíng)管理人員和經(jīng)營(yíng)機(jī)構(gòu)q產(chǎn)品轉(zhuǎn)移v運(yùn)輸克服了產(chǎn)品在生產(chǎn)與需求之間存在的空間和時(shí)間上的差異。q產(chǎn)品存儲(chǔ)v對(duì)產(chǎn)品進(jìn)行臨時(shí)存儲(chǔ)是指將運(yùn)輸車輛臨時(shí)作為相當(dāng)昂貴的存儲(chǔ)設(shè)施。運(yùn)輸?shù)墓δ苓\(yùn)輸?shù)墓δ苓\(yùn)輸服務(wù)的特征運(yùn)輸服務(wù)的特征q運(yùn)輸服務(wù)是一種特殊的產(chǎn)品：運(yùn)輸服務(wù)是一種特殊的產(chǎn)品：v運(yùn)輸服務(wù)產(chǎn)品具有無形性運(yùn)輸服務(wù)產(chǎn)品具有無形性v運(yùn)輸服務(wù)的生產(chǎn)和消費(fèi)不可分離運(yùn)輸服務(wù)的生產(chǎn)和消費(fèi)不可分離v運(yùn)輸服務(wù)具有不可存儲(chǔ)性運(yùn)輸服務(wù)具有不可存儲(chǔ)性v異質(zhì)性，即同一種服務(wù)的質(zhì)量差別異質(zhì)性，即同一種服務(wù)的質(zhì)量差別 6.2 運(yùn)輸方式及其特征運(yùn)輸方式及其特征一、鐵路運(yùn)輸一、鐵路運(yùn)輸l 鐵路是國(guó)民經(jīng)濟(jì)的大動(dòng)脈，鐵路運(yùn)輸是我國(guó)貨物運(yùn)輸

4、的主要鐵路是國(guó)民經(jīng)濟(jì)的大動(dòng)脈，鐵路運(yùn)輸是我國(guó)貨物運(yùn)輸?shù)闹饕绞?。鐵路運(yùn)輸?shù)闹饕攸c(diǎn)是能夠遠(yuǎn)距離運(yùn)輸大量貨物。由方式。鐵路運(yùn)輸?shù)闹饕攸c(diǎn)是能夠遠(yuǎn)距離運(yùn)輸大量貨物。由于世界上幾乎所有的大都市、我國(guó)的絕大部分城市都通鐵路，于世界上幾乎所有的大都市、我國(guó)的絕大部分城市都通鐵路，鐵路在國(guó)際、國(guó)內(nèi)運(yùn)輸中占有相當(dāng)大的市場(chǎng)份額。鐵路在國(guó)際、國(guó)內(nèi)運(yùn)輸中占有相當(dāng)大的市場(chǎng)份額。 l 雖然設(shè)備和站點(diǎn)等的限制使得鐵路運(yùn)營(yíng)的固定成本很高，但雖然設(shè)備和站點(diǎn)等的限制使得鐵路運(yùn)營(yíng)的固定成本很高，但是鐵路運(yùn)營(yíng)的變動(dòng)成本（如維修、管理、耗能等）相對(duì)較低，是鐵路運(yùn)營(yíng)的變動(dòng)成本（如維修、管理、耗能等）相對(duì)較低，這也使得鐵路運(yùn)輸?shù)目偝杀?/p>

5、通常比公路和航空運(yùn)輸?shù)汀＿@也使得鐵路運(yùn)輸?shù)目偝杀就ǔ１裙泛秃娇者\(yùn)輸?shù)?。l 高固定成本和低變動(dòng)成本使鐵路運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)十分明顯。鐵路運(yùn)輸鐵路運(yùn)輸鐵路運(yùn)輸方式的鐵路運(yùn)輸方式的主要優(yōu)點(diǎn)：n運(yùn)輸能力大運(yùn)輸能力大 n運(yùn)行速度較快，時(shí)速一般運(yùn)行速度較快，時(shí)速一般在在8080120120公里公里 n適應(yīng)性強(qiáng)，受天氣限制條適應(yīng)性強(qiáng)，受天氣限制條件少，安全可靠性高件少，安全可靠性高 n運(yùn)輸成本低運(yùn)輸成本低 n環(huán)境污染小，環(huán)境成本低環(huán)境污染小，環(huán)境成本低 鐵路運(yùn)輸方式的鐵路運(yùn)輸方式的主要缺點(diǎn) ：u靈活性差靈活性差u對(duì)包裝的要求較高對(duì)包裝的要求較高u存在貨物被偷盜的危險(xiǎn)存在貨物被偷盜的危險(xiǎn)u鐵路設(shè)施修建成本較高，

6、鐵路設(shè)施修建成本較高，占地多。占地多。6.2 6.2 運(yùn)輸方式及其特征運(yùn)輸方式及其特征二、公路運(yùn)輸二、公路運(yùn)輸l 公路運(yùn)輸具有規(guī)模巨大，分布極廣的道路基礎(chǔ)設(shè)施體系和公路運(yùn)輸具有規(guī)模巨大，分布極廣的道路基礎(chǔ)設(shè)施體系和機(jī)動(dòng)靈活、適應(yīng)性強(qiáng)的車輛裝備系統(tǒng)。大多數(shù)的消費(fèi)品都機(jī)動(dòng)靈活、適應(yīng)性強(qiáng)的車輛裝備系統(tǒng)。大多數(shù)的消費(fèi)品都是通過公路運(yùn)輸?shù)摹Ｊ峭ㄟ^公路運(yùn)輸?shù)?。l 公路運(yùn)輸是任何公司物流系統(tǒng)中重要的一部分。l 公路運(yùn)輸?shù)墓潭ǔ杀竞艿?。汽車承運(yùn)人在固定基礎(chǔ)設(shè)施的公路運(yùn)輸?shù)墓潭ǔ杀竞艿?。汽車承運(yùn)人在固定基礎(chǔ)設(shè)施的投資相對(duì)較少，多數(shù)公路的建設(shè)運(yùn)營(yíng)由政府進(jìn)行。投資相對(duì)較少，多數(shù)公路的建設(shè)運(yùn)營(yíng)由政府進(jìn)行。l 公路運(yùn)輸

7、的變動(dòng)成本相對(duì)較高，因?yàn)楣返慕ㄔO(shè)和維修費(fèi)公路運(yùn)輸?shù)淖儎?dòng)成本相對(duì)較高，因?yàn)楣返慕ㄔO(shè)和維修費(fèi)用經(jīng)常是以稅收和收費(fèi)站的形式向承運(yùn)人征收的。此外，用經(jīng)常是以稅收和收費(fèi)站的形式向承運(yùn)人征收的。此外，汽車的能耗、維修費(fèi)用相對(duì)也比較高。汽車的能耗、維修費(fèi)用相對(duì)也比較高。l 燃油稅燃油稅公路運(yùn)輸公路運(yùn)輸 公路運(yùn)輸方式的主要優(yōu)點(diǎn)：公路運(yùn)輸方式的主要優(yōu)點(diǎn)：q原始投資少，資金周轉(zhuǎn)快，原始投資少，資金周轉(zhuǎn)快，投資回收期短投資回收期短q機(jī)動(dòng)靈活，門對(duì)門運(yùn)輸機(jī)動(dòng)靈活，門對(duì)門運(yùn)輸 q快捷可控快捷可控 q包裝成本低，貨物損失小包裝成本低，貨物損失小 公路運(yùn)輸?shù)闹饕秉c(diǎn)公路運(yùn)輸?shù)闹饕秉c(diǎn) ：運(yùn)輸能力小運(yùn)輸能力小勞動(dòng)生產(chǎn)率低

8、，單位運(yùn)價(jià)勞動(dòng)生產(chǎn)率低，單位運(yùn)價(jià)高高 公路擁擠與污染，環(huán)境成公路擁擠與污染，環(huán)境成本高本高 公路運(yùn)輸不像其它運(yùn)輸方式那樣受到各種線路的限制，其市場(chǎng)覆蓋面要高于其它運(yùn)輸方式。公路運(yùn)輸?shù)奶攸c(diǎn)使得公路運(yùn)輸尤其適于短距離、高價(jià)值產(chǎn)品的裝運(yùn)，在中間產(chǎn)品和輕工產(chǎn)品的運(yùn)輸方面有較大的優(yōu)勢(shì)。 6.26.2運(yùn)輸方式及其特征運(yùn)輸方式及其特征三、水路運(yùn)輸三、水路運(yùn)輸l 水路運(yùn)輸在世界外貿(mào)運(yùn)輸中始終保持主導(dǎo)地位，在經(jīng)濟(jì)合作水路運(yùn)輸在世界外貿(mào)運(yùn)輸中始終保持主導(dǎo)地位，在經(jīng)濟(jì)合作和交流中起著紐帶作用。和交流中起著紐帶作用。l 受自然條件的制約，水路運(yùn)輸?shù)倪\(yùn)營(yíng)范圍和運(yùn)輸速度受到限受自然條件的制約，水路運(yùn)輸?shù)倪\(yùn)營(yíng)范圍和運(yùn)輸速度

9、受到限制，但是卻有其它運(yùn)輸方式不可比擬的優(yōu)勢(shì)和潛力。制，但是卻有其它運(yùn)輸方式不可比擬的優(yōu)勢(shì)和潛力。l 水運(yùn)中水道的改良維護(hù)通常由政府負(fù)責(zé)，港口的開發(fā)和維護(hù)水運(yùn)中水道的改良維護(hù)通常由政府負(fù)責(zé)，港口的開發(fā)和維護(hù)各國(guó)不同，但一般也由政府統(tǒng)一進(jìn)行，而運(yùn)輸公司只需支付各國(guó)不同，但一般也由政府統(tǒng)一進(jìn)行，而運(yùn)輸公司只需支付一定的費(fèi)用就可以使用港口和其它碼頭設(shè)施。一定的費(fèi)用就可以使用港口和其它碼頭設(shè)施。l 水路運(yùn)輸?shù)乃愤\(yùn)輸?shù)?，主要包括運(yùn)營(yíng)中的成本，其規(guī)模主要包括運(yùn)營(yíng)中的成本，其規(guī)模經(jīng)濟(jì)的效應(yīng)更加明顯。經(jīng)濟(jì)的效應(yīng)更加明顯。水路運(yùn)輸水路運(yùn)輸 水路運(yùn)輸方式的主要優(yōu)點(diǎn)：水路運(yùn)輸方式的主要優(yōu)點(diǎn)：?jiǎn)挝贿\(yùn)輸工具的裝載量大

10、，單位運(yùn)輸工具的裝載量大，運(yùn)輸能力高，運(yùn)輸距離長(zhǎng)運(yùn)輸能力高，運(yùn)輸距離長(zhǎng) 水路運(yùn)輸成本低，基礎(chǔ)設(shè)水路運(yùn)輸成本低，基礎(chǔ)設(shè)施投資節(jié)省，單位運(yùn)價(jià)低施投資節(jié)省，單位運(yùn)價(jià)低廉廉 能源消耗少能源消耗少 水路運(yùn)輸方式的主要缺點(diǎn)：水路運(yùn)輸方式的主要缺點(diǎn)：q運(yùn)輸速度慢運(yùn)輸速度慢 q受天氣和其它自然條件影受天氣和其它自然條件影響大，線路迂回響大，線路迂回 q貨物破損較多貨物破損較多 q可靠性差可靠性差 與上述特點(diǎn)相對(duì)應(yīng)，水路運(yùn)輸適于運(yùn)送數(shù)量巨大、低價(jià)值、時(shí)效性要求不高的貨物，如礦石、煤炭、石油農(nóng)產(chǎn)品等。水路運(yùn)輸是大宗貨物長(zhǎng)距離運(yùn)輸?shù)睦硐脒x擇。 6.2 6.2 運(yùn)輸方式及其特征運(yùn)輸方式及其特征四、航空運(yùn)輸四、航空運(yùn)輸

11、l 航空貨運(yùn)的主要優(yōu)點(diǎn)在于運(yùn)輸速度快。航空貨運(yùn)的主要優(yōu)點(diǎn)在于運(yùn)輸速度快。l 隨著航空運(yùn)輸技術(shù)的不斷成熟，航空運(yùn)輸在遠(yuǎn)距離運(yùn)輸，特隨著航空運(yùn)輸技術(shù)的不斷成熟，航空運(yùn)輸在遠(yuǎn)距離運(yùn)輸，特別是跨國(guó)運(yùn)輸中顯示出無可比擬的優(yōu)勢(shì)。別是跨國(guó)運(yùn)輸中顯示出無可比擬的優(yōu)勢(shì)。l 只有在運(yùn)輸高價(jià)值的和對(duì)時(shí)效性要求高于對(duì)成本要求的產(chǎn)品只有在運(yùn)輸高價(jià)值的和對(duì)時(shí)效性要求高于對(duì)成本要求的產(chǎn)品時(shí)，航空運(yùn)輸才有其合理性。時(shí)，航空運(yùn)輸才有其合理性。l 航空的固定成本較低。空中航線和管制系統(tǒng)由國(guó)家擁有，航航空的固定成本較低。空中航線和管制系統(tǒng)由國(guó)家擁有，航空港的建設(shè)運(yùn)營(yíng)由國(guó)家投資，航空公司的固定成本主要與購(gòu)空港的建設(shè)運(yùn)營(yíng)由國(guó)家投資，航

12、空公司的固定成本主要與購(gòu)買飛機(jī)有關(guān)，也與所需的搬運(yùn)系統(tǒng)和貨物集裝箱有關(guān)。買飛機(jī)有關(guān)，也與所需的搬運(yùn)系統(tǒng)和貨物集裝箱有關(guān)。l 航空運(yùn)輸?shù)淖儎?dòng)成本是極高的，其燃料消耗、飛行器的維修航空運(yùn)輸?shù)淖儎?dòng)成本是極高的，其燃料消耗、飛行器的維修保養(yǎng)以及飛行人員和地勤人員的費(fèi)用都是一筆可觀的支出。保養(yǎng)以及飛行人員和地勤人員的費(fèi)用都是一筆可觀的支出。航空運(yùn)輸航空運(yùn)輸航空運(yùn)輸?shù)闹饕獌?yōu)點(diǎn)：航空運(yùn)輸?shù)闹饕獌?yōu)點(diǎn)：u運(yùn)行速度快運(yùn)行速度快 u靈活、機(jī)動(dòng)性大靈活、機(jī)動(dòng)性大 u航空運(yùn)輸服務(wù)質(zhì)量高、安航空運(yùn)輸服務(wù)質(zhì)量高、安全可靠全可靠 航空運(yùn)輸?shù)闹饕秉c(diǎn)：航空運(yùn)輸?shù)闹饕秉c(diǎn)：u運(yùn)輸成本高運(yùn)輸成本高 u運(yùn)輸能力小運(yùn)輸能力小 u有些貨

13、物禁用空運(yùn)有些貨物禁用空運(yùn) u受天氣影響較大受天氣影響較大 綜合上述優(yōu)缺點(diǎn)，航空運(yùn)輸適用于長(zhǎng)途旅客運(yùn)輸和緊急需要的、時(shí)效性要求高的、單位價(jià)值高的貨物運(yùn)輸。 6.2 運(yùn)輸方式及其特征運(yùn)輸方式及其特征q五、管道運(yùn)輸五、管道運(yùn)輸q管道是很獨(dú)特的運(yùn)輸方式，它所能運(yùn)送的貨物種類很有限，管道是很獨(dú)特的運(yùn)輸方式，它所能運(yùn)送的貨物種類很有限，主要通過管道運(yùn)輸?shù)呢浳锸牵菏图俺善酚?、天然氣、化主要通過管道運(yùn)輸?shù)呢浳锸牵菏图俺善酚汀⑻烊粴?、化學(xué)制品。學(xué)制品。q管道運(yùn)輸?shù)膬?yōu)勢(shì)：管道運(yùn)輸?shù)膬?yōu)勢(shì)：v 費(fèi)用低。費(fèi)用低。v 貨損、貨差率低。貨損、貨差率低。v 另外，因?yàn)楣艿肋\(yùn)輸速度很慢，還可以將管道作為倉(cāng)庫(kù)。另外，因?yàn)楣?/p>

14、道運(yùn)輸速度很慢，還可以將管道作為倉(cāng)庫(kù)。v 可靠性好、不受天氣影響、很少有機(jī)械故障可靠性好、不受天氣影響、很少有機(jī)械故障q管道運(yùn)輸?shù)娜秉c(diǎn)：管道運(yùn)輸?shù)娜秉c(diǎn)：v 管道線路是相對(duì)固定的，因此有地域靈活性或可達(dá)性的限制。管道線路是相對(duì)固定的，因此有地域靈活性或可達(dá)性的限制。v 管道運(yùn)輸?shù)漠a(chǎn)品有局限性，并且只能提供單向服務(wù)。管道運(yùn)輸?shù)漠a(chǎn)品有局限性，并且只能提供單向服務(wù)。各種運(yùn)輸方式技術(shù)經(jīng)濟(jì)特征比較表各種運(yùn)輸方式技術(shù)經(jīng)濟(jì)特征比較表運(yùn)輸方運(yùn)輸方式式基建投資基建投資運(yùn)載運(yùn)載量量運(yùn)輸成運(yùn)輸成本本速速度度連續(xù)連續(xù)性性靈活靈活性性生產(chǎn)生產(chǎn)率率安全安全性性線路線路運(yùn)具運(yùn)具鐵路鐵路6 62 22 24 43 31 13

15、34 43 3河運(yùn)河運(yùn)3 34 43 32 26 66 64 42 24 4海運(yùn)海運(yùn)1 13 31 11 15 55 55 51 15 5公路公路4 45 55 55 52 22 21 16 66 6管道管道5 51 14 43 34 43 36 63 31 1航空航空2 26 66 66 61 14 42 25 52 2 注：表中數(shù)字表示各種運(yùn)輸方式在某一方面的優(yōu)劣次序。注：表中數(shù)字表示各種運(yùn)輸方式在某一方面的優(yōu)劣次序。影響運(yùn)輸決策的成本因素影響運(yùn)輸決策的成本因素q影響承運(yùn)人定價(jià)的成本因素影響承運(yùn)人定價(jià)的成本因素v與運(yùn)距有關(guān)的成本與運(yùn)距有關(guān)的成本v與運(yùn)量有關(guān)的成本與運(yùn)量有關(guān)的成本v與速度有關(guān)

16、的成本與速度有關(guān)的成本直送v.s中轉(zhuǎn)q影響承運(yùn)人運(yùn)力組合的成本因素影響承運(yùn)人運(yùn)力組合的成本因素v固定成本固定成本v運(yùn)營(yíng)成本運(yùn)營(yíng)成本運(yùn)輸特性運(yùn)輸特性q規(guī)模規(guī)模特性特性q隨著一次裝運(yùn)量的增大，使每單位重量的運(yùn)輸成本下降。隨著一次裝運(yùn)量的增大，使每單位重量的運(yùn)輸成本下降。q距離距離特性特性q隨著一次運(yùn)輸距離的增加，運(yùn)輸費(fèi)用的增加會(huì)變的越來越緩慢，或者隨著一次運(yùn)輸距離的增加，運(yùn)輸費(fèi)用的增加會(huì)變的越來越緩慢，或者說單位運(yùn)輸距離的費(fèi)用減少，運(yùn)輸成本與一次運(yùn)輸?shù)木嚯x有關(guān)。說單位運(yùn)輸距離的費(fèi)用減少，運(yùn)輸成本與一次運(yùn)輸?shù)木嚯x有關(guān)。q速度速度特性特性q完成特定的運(yùn)輸所需的時(shí)間越短，其效用價(jià)值越高。完成特定的運(yùn)輸所

17、需的時(shí)間越短，其效用價(jià)值越高。單位貨物運(yùn)輸成本運(yùn)輸距離單位貨物運(yùn)輸成本裝載重量運(yùn)輸效用送達(dá)時(shí)間影響承運(yùn)人運(yùn)力組合的成本因素影響承運(yùn)人運(yùn)力組合的成本因素qn the number of time periods into which the time horizon of a year is decomposed (for example, n = 52 if the time period corresponds to a week)qv the decision variable corresponding to the number of owned vehiclesqvt , t = 1

18、,.,n, the required number of vehicles at time period t;qm the number of time periods per year in which vt v.qcF fixed cost （ an owned vehicle）qcV variable cost （ an owned vehicle）qcH be the cost per time period of hiring a vehicle (clearly, c F + c V c H ). qAs the two summations in Equation are equ

19、al to the areas below and above the line vt = v, respectively , then their derivatives are equal to m and m, respectively. qConsequently, C(v) is minimal when影響托運(yùn)人決策的成本因素影響托運(yùn)人決策的成本因素v服務(wù)水平成本（運(yùn)輸時(shí)間-速度）v運(yùn)輸成本（運(yùn)輸方式、運(yùn)輸規(guī)模）v庫(kù)存成本v交易成本運(yùn)輸服務(wù)的選擇運(yùn)輸服務(wù)的選擇q 的影響是決策者心目中的影響是決策者心目中最重要的運(yùn)輸服務(wù)要素，因此，這三項(xiàng)是運(yùn)輸服最重要的運(yùn)輸服務(wù)要素，因此，這三項(xiàng)是運(yùn)

20、輸服務(wù)選擇的基礎(chǔ)。務(wù)選擇的基礎(chǔ)。q運(yùn)輸對(duì)庫(kù)存的影響有以下幾點(diǎn)：運(yùn)輸對(duì)庫(kù)存的影響有以下幾點(diǎn)：q在選擇運(yùn)輸方式時(shí)，就需要考慮庫(kù)存持有成本可在選擇運(yùn)輸方式時(shí)，就需要考慮庫(kù)存持有成本可能升高，而抵消運(yùn)輸服務(wù)成本降低的情況。能升高，而抵消運(yùn)輸服務(wù)成本降低的情況。運(yùn)輸服務(wù)的選擇的定量分析法運(yùn)輸服務(wù)的選擇的定量分析法q基于運(yùn)輸成本與庫(kù)存成本的總成本分析方法基于運(yùn)輸成本與庫(kù)存成本的總成本分析方法v【例例】某公司欲將產(chǎn)品從位置某公司欲將產(chǎn)品從位置A的工廠運(yùn)往位的工廠運(yùn)往位置置B的公司自有倉(cāng)庫(kù)，年運(yùn)量的公司自有倉(cāng)庫(kù)，年運(yùn)量D=700000件，件，產(chǎn)品價(jià)值產(chǎn)品價(jià)值C=30元，年存貨成本元，年存貨成本I=產(chǎn)品價(jià)格的產(chǎn)

21、品價(jià)格的30。公司希望選擇使總成本最小的運(yùn)輸方式。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫(kù)存成本據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫(kù)存成本可以減少可以減少1。各種運(yùn)輸服務(wù)方式的有關(guān)參數(shù)。各種運(yùn)輸服務(wù)方式的有關(guān)參數(shù)見表：見表：運(yùn)輸服務(wù)的選擇的定量分析法運(yùn)輸服務(wù)的選擇的定量分析法運(yùn)輸方式運(yùn)輸方式 費(fèi)率費(fèi)率R(元元/件件) 時(shí)間時(shí)間T(天天) 年運(yùn)送批年運(yùn)送批次次 平均存貨平均存貨量量Q/2 鐵路鐵路 0.12110100000水運(yùn)水運(yùn) 0路公路 0.252042000航空航空1.424020250運(yùn)輸服務(wù)的選擇的定量分析法運(yùn)輸服務(wù)的選擇的定量分

22、析法q分析：分析：v以年總成本最低為原則來選擇合適的運(yùn)輸方式。這里，以年總成本最低為原則來選擇合適的運(yùn)輸方式。這里，總成本總成本=運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用+庫(kù)存成本；庫(kù)存成本；v其中，其中，運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用=運(yùn)輸量運(yùn)輸量 費(fèi)率費(fèi)率v庫(kù)存成本庫(kù)存成本=在途運(yùn)輸庫(kù)存成本在途運(yùn)輸庫(kù)存成本+工廠存貨成本工廠存貨成本+倉(cāng)庫(kù)存?zhèn)}庫(kù)存貨成本貨成本v在途運(yùn)輸庫(kù)存費(fèi)用在途運(yùn)輸庫(kù)存費(fèi)用=ICDT/365v工廠存貨成本工廠存貨成本=ICQ/2v倉(cāng)庫(kù)存貨成本倉(cāng)庫(kù)存貨成本=I（C+R）Q/2v代入各種運(yùn)輸方式的基本數(shù)據(jù)信息，將相應(yīng)的成本計(jì)算代入各種運(yùn)輸方式的基本數(shù)據(jù)信息，將相應(yīng)的成本計(jì)算結(jié)果列入表結(jié)果列入表2。vD年運(yùn)量；年運(yùn)

23、量；C產(chǎn)品單價(jià)；產(chǎn)品單價(jià)； I年存貨成本（產(chǎn)品價(jià)年存貨成本（產(chǎn)品價(jià)格的格的30）；）；vT運(yùn)輸時(shí)間；運(yùn)輸時(shí)間； R費(fèi)率費(fèi)率 (元元/件件) ； Q/2平均存貨量平均存貨量二、運(yùn)輸方式選擇的定量分析法二、運(yùn)輸方式選擇的定量分析法由表中結(jié)果可知，總成本最低的是公路運(yùn)輸方式，總成本為由表中結(jié)果可知，總成本最低的是公路運(yùn)輸方式，總成本為984821元，其次是水路運(yùn)輸，成本最高的是鐵路運(yùn)輸。按照元，其次是水路運(yùn)輸，成本最高的是鐵路運(yùn)輸。按照總成本最低的原則，適合選擇公路運(yùn)輸方式?？偝杀咀畹偷脑瓌t，適合選擇公路運(yùn)輸方式。 成本類成本類型型 計(jì)算公式計(jì)算公式 鐵路運(yùn)輸鐵路運(yùn)輸 水路運(yùn)輸水路運(yùn)輸 公路運(yùn)輸公路

24、運(yùn)輸 航空運(yùn)輸航空運(yùn)輸 運(yùn)輸成運(yùn)輸成本本 R D 70000105000140000980000在途庫(kù)在途庫(kù)存存 ICDT/365 345205241644 8630134521工廠存工廠存貨貨 ICQ/2 900000416500378000182250倉(cāng)庫(kù)存?zhèn)}庫(kù)存貨貨 I(C+R)Q/2903000420593380520190755總成本總成本 2218205118573798482113875266.4運(yùn)輸路線的選擇運(yùn)輸路線的選擇q1 1起、止點(diǎn)不同的單一路徑規(guī)劃起、止點(diǎn)不同的單一路徑規(guī)劃q2 2多個(gè)起、止點(diǎn)的路徑規(guī)劃多個(gè)起、止點(diǎn)的路徑規(guī)劃q3 3起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃起點(diǎn)和終點(diǎn)相同

25、的路徑規(guī)劃vTraveling Salesman Problem (TSP)Traveling Salesman Problem (TSP)vVehicle Routing Problem (VRP)Vehicle Routing Problem (VRP)6.4運(yùn)輸路線的選擇運(yùn)輸路線的選擇q1起、止點(diǎn)不同的單一路徑規(guī)劃起、止點(diǎn)不同的單一路徑規(guī)劃q這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為基礎(chǔ)的問題之一。q問題描述：假設(shè)有一n個(gè)節(jié)點(diǎn)和m條弧的連通圖G（Vn,Em),并且圖中的每條?。╥,j)都有一個(gè)長(zhǎng)度cij(或者費(fèi)用cij)，q求解此類最短路徑問題，主要有以下幾種算

26、法：q（1）Dijkstra算法；（2）Floyd算法；（3）逐次逼近法1起、止點(diǎn)不同的單一路徑規(guī)劃起、止點(diǎn)不同的單一路徑規(guī)劃例例 某運(yùn)輸公司簽訂了一項(xiàng)運(yùn)輸合同，要把A市的一批貨物運(yùn)送到B市，該公司根據(jù)這兩個(gè)城市之間可選擇的行車路線的地圖繪制了如圖所示的公路網(wǎng)絡(luò)。圖中，圓圈也稱節(jié)點(diǎn)，代表起點(diǎn)、目的地和與行車路線相交的其他城市。鏈代表兩個(gè)結(jié)點(diǎn)之間的公路，每一條公路都標(biāo)明運(yùn)輸里程。A市市B市市解答：最短路的計(jì)算方法解答：最短路的計(jì)算方法（1 1）找出第）找出第n n個(gè)距起點(diǎn)最近的節(jié)點(diǎn)。對(duì)個(gè)距起點(diǎn)最近的節(jié)點(diǎn)。對(duì)n=1,2,n=1,2,，重復(fù)此過程，直到所，重復(fù)此過程，直到所找出的最近節(jié)點(diǎn)是終點(diǎn)。找出

27、的最近節(jié)點(diǎn)是終點(diǎn)。（2 2）在前面的迭代過程中找出（）在前面的迭代過程中找出（n-1n-1）個(gè)距起點(diǎn)最近的節(jié)點(diǎn)，及其距起）個(gè)距起點(diǎn)最近的節(jié)點(diǎn)，及其距起點(diǎn)最短的中徑和距離，這些節(jié)點(diǎn)和起點(diǎn)統(tǒng)稱為已解的節(jié)點(diǎn)，其余的稱為點(diǎn)最短的中徑和距離，這些節(jié)點(diǎn)和起點(diǎn)統(tǒng)稱為已解的節(jié)點(diǎn)，其余的稱為未解節(jié)點(diǎn)。未解節(jié)點(diǎn)。（3 3）每個(gè)已解的節(jié)點(diǎn)和一個(gè)或多外未解的節(jié)點(diǎn)相連接，就可以得出一）每個(gè)已解的節(jié)點(diǎn)和一個(gè)或多外未解的節(jié)點(diǎn)相連接，就可以得出一個(gè)候選點(diǎn)個(gè)候選點(diǎn)連接距離最短的未解點(diǎn)。如果有多個(gè)距離相等的最短連接，連接距離最短的未解點(diǎn)。如果有多個(gè)距離相等的最短連接，則有多個(gè)候選點(diǎn)。則有多個(gè)候選點(diǎn)。（4 4）將每個(gè)已解節(jié)點(diǎn)與其候

28、選點(diǎn)之間的距離累加到該已解節(jié)點(diǎn)與起點(diǎn)）將每個(gè)已解節(jié)點(diǎn)與其候選點(diǎn)之間的距離累加到該已解節(jié)點(diǎn)與起點(diǎn)之間最短路徑的距離上，所得出的總距離最短的候選點(diǎn)就是第之間最短路徑的距離上，所得出的總距離最短的候選點(diǎn)就是第n n個(gè)最近個(gè)最近的節(jié)點(diǎn)，其最短路徑就是得出該距離的路徑（若多個(gè)候選點(diǎn)都得出相等的節(jié)點(diǎn)，其最短路徑就是得出該距離的路徑（若多個(gè)候選點(diǎn)都得出相等的最短距離，則都是已解節(jié)點(diǎn)）。的最短距離，則都是已解節(jié)點(diǎn)）。通過上表的計(jì)算，最短路徑為通過上表的計(jì)算，最短路徑為1-2-5-4-3-6，最短距離為，最短距離為12。FloydFloyd算法算法qF F算法的基本思路算法的基本思路: :qF算法使用距離矩陣距

29、離矩陣和路由矩陣路由矩陣。q距離矩陣距離矩陣是一個(gè)nn矩陣，以圖G的n個(gè)節(jié)點(diǎn)為行和列。記為W=w wijij n n， w wijij表示圖G中vi和vj兩點(diǎn)之間的路徑長(zhǎng)度。q路由矩陣路由矩陣是一個(gè)nn矩陣，以圖G的n個(gè)節(jié)點(diǎn)為行和列。記為R =r rijij n n ，其中r rijij表示vi至vj經(jīng)過的轉(zhuǎn)接點(diǎn)（中間節(jié)點(diǎn)）。F算法的思路是首先寫出初始的W陣和R陣，接著按順序依次將節(jié)點(diǎn)集中的各個(gè)節(jié)點(diǎn)作為中間節(jié)點(diǎn)，計(jì)算此點(diǎn)距其他各點(diǎn)的徑長(zhǎng)，每次計(jì)算后都以求得的與上次相比較小的徑長(zhǎng)去更新前一次較大徑長(zhǎng)，若后求得的徑長(zhǎng)比前次徑長(zhǎng)大或相等則不變。以此不斷更新和，直至W中的數(shù)值收斂。按順序，依次作為中間

30、節(jié)點(diǎn)，（按順序，后面的點(diǎn)不作為（按順序，后面的點(diǎn)不作為中間節(jié)點(diǎn)）中間節(jié)點(diǎn)）考察所有所有通過此中間節(jié)點(diǎn)的路徑1245310561543123451310235310615456454W0123451234521345312454123551234R012453105615431234513102313531013615456454W1123451234521145311454123551234R11245310561543123451310823135310136154856454W2123451232521145311454223551234R2124531056154312345131082

31、52313528310136154856454W3123451232321143311454223551234R3124531056154312345131081223115931011610485645129104D4123451232421444314444223554444S42多個(gè)起、止點(diǎn)的路徑規(guī)劃當(dāng)有多個(gè)貨源和多個(gè)目的地時(shí)，就需要指定目的地的供貨地，同時(shí)當(dāng)有多個(gè)貨源和多個(gè)目的地時(shí)，就需要指定目的地的供貨地，同時(shí)要找到供貨地、目的地之間的最佳路徑。要找到供貨地、目的地之間的最佳路徑。例例 某公司下屬三個(gè)倉(cāng)庫(kù)，供應(yīng)四個(gè)客戶的需要，三個(gè)倉(cāng)庫(kù)的供應(yīng)量某公司下屬三個(gè)倉(cāng)庫(kù)，供應(yīng)四個(gè)客戶的需要，三

32、個(gè)倉(cāng)庫(kù)的供應(yīng)量和四個(gè)客戶的需求量，以及由各倉(cāng)庫(kù)到各客戶的運(yùn)輸單價(jià)如下表所示。和四個(gè)客戶的需求量，以及由各倉(cāng)庫(kù)到各客戶的運(yùn)輸單價(jià)如下表所示。求運(yùn)輸費(fèi)用最少的運(yùn)輸方案。求運(yùn)輸費(fèi)用最少的運(yùn)輸方案。 銷地銷地客戶客戶1客戶客戶2客戶客戶3客戶客戶4供應(yīng)量供應(yīng)量運(yùn)價(jià)運(yùn)價(jià)產(chǎn)地產(chǎn)地倉(cāng)庫(kù)倉(cāng)庫(kù)A311310700倉(cāng)庫(kù)倉(cāng)庫(kù)B1928400倉(cāng)庫(kù)倉(cāng)庫(kù)C74105900需求量需求量3006005006002000表上做業(yè)法表上做業(yè)法，該方法適合于對(duì)相對(duì)簡(jiǎn)單的問題進(jìn)行求解，求解過程方便，該方法適合于對(duì)相對(duì)簡(jiǎn)單的問題進(jìn)行求解，求解過程方便直觀，而且由于計(jì)算量不大，可以用手工直接完成。利用表上作業(yè)法有兩直觀，而且由于計(jì)算量不

33、大，可以用手工直接完成。利用表上作業(yè)法有兩個(gè)基本步驟：個(gè)基本步驟：（1 1）確定初始調(diào)運(yùn)方案）確定初始調(diào)運(yùn)方案 最小元素法是按運(yùn)價(jià)表依次挑選運(yùn)費(fèi)小的供最小元素法是按運(yùn)價(jià)表依次挑選運(yùn)費(fèi)小的供- -需點(diǎn)組合，盡量?jī)?yōu)需點(diǎn)組合，盡量?jī)?yōu)先安排運(yùn)費(fèi)最低組合的方法。先安排運(yùn)費(fèi)最低組合的方法。 3113101928734105 銷銷地地客戶客戶1客戶客戶2客戶客戶3客戶客戶4供應(yīng)量供應(yīng)量運(yùn)價(jià)運(yùn)價(jià)產(chǎn)地產(chǎn)地倉(cāng)庫(kù)倉(cāng)庫(kù)A400300700倉(cāng)庫(kù)倉(cāng)庫(kù)B300100400倉(cāng)庫(kù)倉(cāng)庫(kù)C600300900需求量需求量300600500600表表5.4 初始調(diào)運(yùn)方案初始調(diào)運(yùn)方案（2 2）初始方案的檢驗(yàn)）初始方案的檢驗(yàn)最優(yōu)方案的數(shù)字

34、特征最優(yōu)方案的數(shù)字特征檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：閉回路：閉回路： 從理論上講，對(duì)于表上作業(yè)法的初始方案來說，從調(diào)運(yùn)方案從理論上講，對(duì)于表上作業(yè)法的初始方案來說，從調(diào)運(yùn)方案表上的一個(gè)空格出發(fā)，存在一條且僅存在一條以該表上的一個(gè)空格出發(fā)，存在一條且僅存在一條以該空格空格（用（用xijxij表表示）為起點(diǎn)，以示）為起點(diǎn)，以其他填有數(shù)字的點(diǎn)其他填有數(shù)字的點(diǎn)為其他頂點(diǎn)的閉合回路，簡(jiǎn)稱閉為其他頂點(diǎn)的閉合回路，簡(jiǎn)稱閉回路。這個(gè)閉回路有以下性質(zhì)：回路。這個(gè)閉回路有以下性質(zhì)：每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn)；每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn)；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行（

35、列）若有閉合回路的頂點(diǎn)，則必有兩個(gè)。每一行（列）若有閉合回路的頂點(diǎn)，則必有兩個(gè)。 只有從空格出發(fā)，其余各轉(zhuǎn)角點(diǎn)所對(duì)應(yīng)的方格內(nèi)均填寫數(shù)字時(shí)，只有從空格出發(fā)，其余各轉(zhuǎn)角點(diǎn)所對(duì)應(yīng)的方格內(nèi)均填寫數(shù)字時(shí)，所構(gòu)成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉所構(gòu)成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。合回路不僅是存在的，而且是唯一的。 銷地銷地客戶客戶1客戶客戶2客戶客戶3客戶客戶4供應(yīng)量供應(yīng)量產(chǎn)地產(chǎn)地倉(cāng)庫(kù)倉(cāng)庫(kù)A400300700倉(cāng)庫(kù)倉(cāng)庫(kù)B300100400倉(cāng)庫(kù)倉(cāng)庫(kù)C600300900需求量需求量300600500600 表表6.56.5給出了單元格（

36、給出了單元格（1 1，1 1）和（）和（3 3，1 1）所形成的閉回路：（）所形成的閉回路：（1 1，1 1）（1,31,3）(2(2，3)3)（2 2，1 1）（1 1，1 1）；（）；（3 3，1 1）（2 2，1 1）（2 2，3 3）（1 1，3 3）（1 1，4 4）（3 3，4 4）（3 3，1 1）。其他空格的閉回路與此同）。其他空格的閉回路與此同理。理。 在調(diào)運(yùn)方案內(nèi)的每個(gè)空格所形成的閉回路上，作單位物資的運(yùn)量調(diào)整，在調(diào)運(yùn)方案內(nèi)的每個(gè)空格所形成的閉回路上，作單位物資的運(yùn)量調(diào)整，總可以計(jì)算出相應(yīng)的運(yùn)費(fèi)是增加還是減少。我們把所計(jì)算出來的每條閉回路上總可以計(jì)算出相應(yīng)的運(yùn)費(fèi)是增加還是減

37、少。我們把所計(jì)算出來的每條閉回路上調(diào)整單位運(yùn)量而使運(yùn)輸費(fèi)用發(fā)生變化的增減值，稱其為檢驗(yàn)數(shù)。調(diào)整單位運(yùn)量而使運(yùn)輸費(fèi)用發(fā)生變化的增減值，稱其為檢驗(yàn)數(shù)。如果檢驗(yàn)數(shù)小如果檢驗(yàn)數(shù)小于于0 0，表示在該空格的閉回路上調(diào)整運(yùn)量會(huì)使運(yùn)費(fèi)減少；相反，如果檢驗(yàn)數(shù)大，表示在該空格的閉回路上調(diào)整運(yùn)量會(huì)使運(yùn)費(fèi)減少；相反，如果檢驗(yàn)數(shù)大于于0 0，則會(huì)使運(yùn)費(fèi)增加。，則會(huì)使運(yùn)費(fèi)增加。表8.5 初始調(diào)運(yùn)方案用閉回路法求檢驗(yàn)數(shù)時(shí)，需給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時(shí)，這種計(jì)算很繁，可以用較為簡(jiǎn)便的方法可以用較為簡(jiǎn)便的方法“位勢(shì)法位勢(shì)法”求解。求解。設(shè)u1,u2,um；v1,v2,vn，是對(duì)應(yīng)運(yùn)輸問題的m+n個(gè)約束條件的對(duì)偶變

38、量。在初始調(diào)運(yùn)方案中x13,x14,x21,x23,x32,x34是基變量，這時(shí)對(duì)應(yīng)的檢驗(yàn)數(shù)是：基變量基變量 檢驗(yàn)數(shù)檢驗(yàn)數(shù)x21 c21-( u2+v1)=0 x21 c21-( u2+v1)=0 設(shè)設(shè)v1=0v1=0，并且，并且c21=1 c21=1 所以所以 u2=1u2=1x23 c23-(u2+v3)=0 2-( u2+v3)=0 x23 c23-(u2+v3)=0 2-( u2+v3)=0 x13 c13-(u1+v3)=0 3-( u1+v3)=0 x13 c13-(u1+v3)=0 3-( u1+v3)=0 x14 c14-(u1+v4)=0 10-( u1+v4)=0 x14

39、c14-(u1+v4)=0 10-( u1+v4)=0 x34 c34-(u3+v4)=0 5-( u3+v4)=0 x34 c34-(u3+v4)=0 5-( u3+v4)=0 x22 c22-(u2+v2)=0 4-( u2+v2)=0 x22 c22-(u2+v2)=0 4-( u2+v2)=0通過這些方程可以求得通過這些方程可以求得u1=2 u2=1 u3= -3 v1=0 v2=7 v3=1 v4=8u1=2 u2=1 u3= -3 v1=0 v2=7 v3=1 v4=8在初始解調(diào)運(yùn)方案中增加一行一列，在初始解調(diào)運(yùn)方案中增加一行一列，在列中填入在列中填入ui,ui,在行中填入在行中填

40、入vivi。接著，。接著，按按ij=cij-(ui+vj)ij=cij-(ui+vj)計(jì)算所有空格的檢驗(yàn)數(shù)。完成后的表格見表計(jì)算所有空格的檢驗(yàn)數(shù)。完成后的表格見表5.65.6。3113101928734105 銷地銷地客戶客戶1客戶客戶2客戶客戶3客戶客戶4ui運(yùn)價(jià)運(yùn)價(jià)產(chǎn)地產(chǎn)地倉(cāng)庫(kù)倉(cāng)庫(kù)A12002倉(cāng)庫(kù)倉(cāng)庫(kù)B010-11倉(cāng)庫(kù)倉(cāng)庫(kù)C100120-3vi0718表表5.6 檢驗(yàn)數(shù)表格檢驗(yàn)數(shù)表格（3 3）方案調(diào)整）方案調(diào)整 判定一個(gè)初始調(diào)運(yùn)方案不是最優(yōu)調(diào)運(yùn)方案的標(biāo)準(zhǔn)，是在檢驗(yàn)數(shù)表格中判定一個(gè)初始調(diào)運(yùn)方案不是最優(yōu)調(diào)運(yùn)方案的標(biāo)準(zhǔn)，是在檢驗(yàn)數(shù)表格中出現(xiàn)負(fù)值的檢驗(yàn)數(shù)。如果檢驗(yàn)數(shù)的負(fù)值不止個(gè)時(shí)，一般選擇負(fù)檢驗(yàn)數(shù)

41、絕對(duì)出現(xiàn)負(fù)值的檢驗(yàn)數(shù)。如果檢驗(yàn)數(shù)的負(fù)值不止個(gè)時(shí)，一般選擇負(fù)檢驗(yàn)數(shù)絕對(duì)值最大的空格作為具體調(diào)整對(duì)象。值最大的空格作為具體調(diào)整對(duì)象。 從表從表5.65.6可以發(fā)現(xiàn)，單元格可以發(fā)現(xiàn)，單元格x x2424的檢驗(yàn)數(shù)是負(fù)數(shù)，因此對(duì)其進(jìn)行調(diào)整，的檢驗(yàn)數(shù)是負(fù)數(shù)，因此對(duì)其進(jìn)行調(diào)整，具體過程如表具體過程如表5.75.7所示。所示。x13400+100=500 x14300-100=200 x23100-100=0 x240+100=100表表5.7 5.7 調(diào)動(dòng)方案調(diào)整表調(diào)動(dòng)方案調(diào)整表 從單元格從單元格x x2424開始，沿閉回路在各奇數(shù)次轉(zhuǎn)角點(diǎn)中挑選運(yùn)量的最小數(shù)值開始，沿閉回路在各奇數(shù)次轉(zhuǎn)角點(diǎn)中挑選運(yùn)量的最小數(shù)

42、值作為調(diào)整量。在此將作為調(diào)整量。在此將x x2323單元格的單元格的100100作為調(diào)整量，將亮個(gè)數(shù)填入單元格作為調(diào)整量，將亮個(gè)數(shù)填入單元格x x2424內(nèi)，內(nèi)，同時(shí)調(diào)整該閉回路中其他轉(zhuǎn)角點(diǎn)上的運(yùn)量，使各行、列保持原來的供需平衡，同時(shí)調(diào)整該閉回路中其他轉(zhuǎn)角點(diǎn)上的運(yùn)量，使各行、列保持原來的供需平衡，這樣注得到一個(gè)新的調(diào)運(yùn)方案，如表這樣注得到一個(gè)新的調(diào)運(yùn)方案，如表5.75.7所示。所示。3113101928734105 銷地客戶客戶1客戶客戶2客戶客戶3客戶客戶4供應(yīng)量供應(yīng)量 運(yùn)價(jià)產(chǎn)地倉(cāng)庫(kù)倉(cāng)庫(kù)A500200700倉(cāng)庫(kù)倉(cāng)庫(kù)B300100400倉(cāng)庫(kù)倉(cāng)庫(kù)C600300900需求量需求量300600500

43、600表表6.7 6.7 調(diào)整后的方案調(diào)整后的方案按新方案計(jì)算調(diào)運(yùn)物資的運(yùn)輸費(fèi)用為：按新方案計(jì)算調(diào)運(yùn)物資的運(yùn)輸費(fèi)用為：3 3500+10500+10200+8200+8100+4100+4600+5600+5300=8500300=8500元元新方案是否最優(yōu)方案，還需再進(jìn)行檢驗(yàn)。經(jīng)計(jì)算，該新方案新方案是否最優(yōu)方案，還需再進(jìn)行檢驗(yàn)。經(jīng)計(jì)算，該新方案的所有檢驗(yàn)數(shù)都是非負(fù)數(shù)，說明該方案已經(jīng)是最優(yōu)方案了。的所有檢驗(yàn)數(shù)都是非負(fù)數(shù)，說明該方案已經(jīng)是最優(yōu)方案了。找出檢驗(yàn)數(shù)找出檢驗(yàn)數(shù) ij為最小負(fù)值的格子的閉回路為最小負(fù)值的格子的閉回路 在滿足所有約束條件的情況下，盡可能增大這在滿足所有約束條件的情況下，盡可

44、能增大這個(gè)格子的個(gè)格子的xij值值 調(diào)整此閉回路上其他頂點(diǎn)的值調(diào)整此閉回路上其他頂點(diǎn)的值 檢驗(yàn)新解的最優(yōu)性檢驗(yàn)新解的最優(yōu)性 重復(fù)上步驟直至得到最優(yōu)解為止。重復(fù)上步驟直至得到最優(yōu)解為止。3起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃起點(diǎn)和終點(diǎn)重合的路徑問題一般被稱為起點(diǎn)和終點(diǎn)重合的路徑問題一般被稱為“旅行商旅行商”問題（問題（TSP, TSP, Traveling Salesman ProblemTraveling Salesman Problem），是運(yùn)籌學(xué)、圖論和組合優(yōu)化中的），是運(yùn)籌學(xué)、圖論和組合優(yōu)化中的典型問題。典型問題。 TSPTSP問題一般描述如下：?jiǎn)栴}一般描述如下：一個(gè)旅行者從

45、出發(fā)地出發(fā)，經(jīng)過所有要到達(dá)的城市后，返回到出發(fā)一個(gè)旅行者從出發(fā)地出發(fā)，經(jīng)過所有要到達(dá)的城市后，返回到出發(fā)地，要求合理安排其旅行路線，地，要求合理安排其旅行路線，使得總旅行距離（或旅行費(fèi)用、旅使得總旅行距離（或旅行費(fèi)用、旅行時(shí)間等）最短。行時(shí)間等）最短。TSPTSP問題特性：?jiǎn)栴}特性：p單一車輛單一車輛p無車輛容量限制無車輛容量限制p求解復(fù)雜度屬于求解復(fù)雜度屬于NP-hard，大規(guī)模問題難以求得最佳解，現(xiàn)，大規(guī)模問題難以求得最佳解，現(xiàn)實(shí)中常采取實(shí)中常采取”啟發(fā)式方法啟發(fā)式方法(Heuristics)“求解求解TSPTSP問題數(shù)學(xué)規(guī)劃模型問題數(shù)學(xué)規(guī)劃模型 Mins.t.ijijijxcAin al

46、lfor 1 , 011ijxNjxNixijiijjijTSPTSP問題求解算法問題求解算法q真正解法真正解法(只能處理非常小的問題只能處理非常小的問題)vEnumeration窮舉法窮舉法vAssignment algorithm指派算法指派算法vLittles method分枝定界法分枝定界法(Branch-and-Bound)q傳統(tǒng)啟發(fā)式解法傳統(tǒng)啟發(fā)式解法(Heuristics)大致可歸納為以下大致可歸納為以下三種：三種：v路線構(gòu)建路線構(gòu)建(route construction)鄰點(diǎn)法、插入法.v路線改善路線改善(route improvement)k-Opt交換法、Or-Opt交換法

47、v綜合型綜合型(composite)合并執(zhí)行路線構(gòu)建及路線改善Assignment Procedure For TSP1 1、將、將A A到到A A，B B到到B,CB,C到到C C的費(fèi)用轉(zhuǎn)換成無限的費(fèi)用轉(zhuǎn)換成無限大，以防止返回。大，以防止返回。Assignment Procedure For TSPq2、應(yīng)用指派、應(yīng)用指派問題的匈牙利問題的匈牙利算法，使得表算法，使得表中不同行、不中不同行、不同列都含有同列都含有0q此時(shí)，若完成此時(shí)，若完成路徑的選擇，路徑的選擇，最少的費(fèi)用為最少的費(fèi)用為9Assignment Procedure For TSPq可行解尚未找到。可行解尚未找到。q此時(shí)考慮此時(shí)

48、考慮 增加一增加一個(gè)個(gè)“費(fèi)用最小的費(fèi)用最小的非非0路徑路徑” ，看，看看是否有可行解?？词欠裼锌尚薪狻５玫剑旱玫剑喝匀粵]有可行解。仍然沒有可行解。此時(shí)考慮此時(shí)考慮 再再增加一個(gè)增加一個(gè)“費(fèi)用最小的非費(fèi)用最小的非0 0路徑路徑” ，或增加一個(gè)或增加一個(gè)“費(fèi)用次小的費(fèi)用次小的非非0 0”路徑看看是否有可行路徑看看是否有可行解。解。得到：得到：Littles method分枝定界法分枝定界法(Branch-and-Bound)q1、計(jì)算出所有不、計(jì)算出所有不走走“0費(fèi)用費(fèi)用”路徑路徑的懲罰成本的懲罰成本q2、選擇懲罰成本、選擇懲罰成本最大的路徑最大的路徑q3、簡(jiǎn)化計(jì)算表，消除已經(jīng)選擇的路徑，形成新的

49、計(jì)算表；、簡(jiǎn)化計(jì)算表，消除已經(jīng)選擇的路徑，形成新的計(jì)算表；繼續(xù)分支定界。繼續(xù)分支定界。同時(shí)，為了防止返回，同時(shí)，為了防止返回，E到到C設(shè)為設(shè)為；再檢查是否每一行、每；再檢查是否每一行、每一列都有一列都有“0費(fèi)用費(fèi)用”路徑，若沒有在此行路徑，若沒有在此行/列減去最小元素。列減去最小元素。E行減去行減去1，得到：，得到：D同時(shí)，為了防止返回，同時(shí)，為了防止返回，E到到B設(shè)為設(shè)為；再檢查是否每一行、每；再檢查是否每一行、每一列都有一列都有“0費(fèi)用費(fèi)用”路徑，若沒有在此行路徑，若沒有在此行/列減去最小元素。列減去最小元素。A列減去列減去1，得到：，得到：假設(shè)選擇假設(shè)選擇E,D路徑，得到：路徑，得到：假

50、設(shè)不選擇假設(shè)不選擇E,D路徑：路徑：傳統(tǒng)啟發(fā)式解法傳統(tǒng)啟發(fā)式解法q1、最近鄰點(diǎn)法、最近鄰點(diǎn)法(Nearest-neighbor Heuristic)1. 任選一節(jié)點(diǎn)為起點(diǎn)任選一節(jié)點(diǎn)為起點(diǎn)x2. 尋找距離節(jié)點(diǎn)尋找距離節(jié)點(diǎn)x最近的節(jié)點(diǎn)最近的節(jié)點(diǎn)y作為下一個(gè)造訪的節(jié)點(diǎn)作為下一個(gè)造訪的節(jié)點(diǎn)3. 尋找距離節(jié)點(diǎn)尋找距離節(jié)點(diǎn)y最近的節(jié)點(diǎn)最近的節(jié)點(diǎn)z作為下一個(gè)造訪的節(jié)點(diǎn)作為下一個(gè)造訪的節(jié)點(diǎn)4. 重復(fù)以上步驟，直到所有節(jié)點(diǎn)均已造訪重復(fù)以上步驟，直到所有節(jié)點(diǎn)均已造訪5. 連接最后一個(gè)節(jié)點(diǎn)與起點(diǎn)，即形成一個(gè)連接最后一個(gè)節(jié)點(diǎn)與起點(diǎn)，即形成一個(gè)TSP的可行解的可行解1、最近鄰點(diǎn)法、最近鄰點(diǎn)法14235743875534

51、8142351234514738247553773443538585482、插入法插入法(Insertion Method)(Insertion Method)1. 任選一節(jié)點(diǎn)為起點(diǎn)任選一節(jié)點(diǎn)為起點(diǎn)a2. 尋找距離節(jié)點(diǎn)尋找距離節(jié)點(diǎn)a最近的節(jié)點(diǎn)最近的節(jié)點(diǎn)b作為下一個(gè)造訪的節(jié)點(diǎn)，作為下一個(gè)造訪的節(jié)點(diǎn)，形成形成a-b-a的子回路的子回路3. 尋找距離子回路最近的節(jié)點(diǎn)尋找距離子回路最近的節(jié)點(diǎn)k作為下一個(gè)插入點(diǎn)作為下一個(gè)插入點(diǎn)4. 尋找插入成本最小的位置尋找插入成本最小的位置(i-j)，將，將k插入插入i-j之間，形之間，形成新的子回路。成新的子回路。插入成本：插入成本：Cik+Ckj-Cij5. 重復(fù)

52、步驟重復(fù)步驟34，直到所有節(jié)點(diǎn)均已插入回路之中，即，直到所有節(jié)點(diǎn)均已插入回路之中，即形成一個(gè)形成一個(gè)TSP的可行解的可行解2、插入法插入法14235743875534814141333373337317224525727421455885845455582145543 3、 2-opt 2-opt 交換交換法法1.先構(gòu)建一個(gè)起始可行解先構(gòu)建一個(gè)起始可行解2.在可行解中任選兩個(gè)不相鄰的節(jié)線在可行解中任選兩個(gè)不相鄰的節(jié)線(a b, c d)，以及另外兩條對(duì)應(yīng)之替換節(jié)線，以及另外兩條對(duì)應(yīng)之替換節(jié)線(a c, b d)，計(jì)算替換后總成本是否降低，計(jì)算替換后總成本是否降低 (即檢查即檢查替換成本是否小于

53、替換成本是否小于0)。 替換成本：替換成本：Cac+Cbd-Cab-Ccd (對(duì)稱型對(duì)稱型TSP)3.若替換后總成本有降低，則予以替換，同時(shí)若替換后總成本有降低，則予以替換，同時(shí)變更中間相關(guān)弧線的行走方向變更中間相關(guān)弧線的行走方向4.重復(fù)步驟重復(fù)步驟23，直到所有可能的替換均無法，直到所有可能的替換均無法再降低成本為止再降低成本為止3 3、 2-opt 2-opt 交換交換法法1423574387553484 4、常見的宏啟發(fā)式方法、常見的宏啟發(fā)式方法(Meta-heuristics)(Meta-heuristics)v禁忌搜索法禁忌搜索法(Tabu Search, TS)v基因算法基因算法(

54、Genetic Algorithm, GA)v模擬退火法模擬退火法(Simulated Annealing, SA)v門限值接受法門限值接受法(Threshold Accepting, TA)v神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)(Neural Network, NN)v蟻群算法蟻群算法(Ant Colony Optimization, ACO)v其它其它6.4 車輛路線、時(shí)間安排車輛路線、時(shí)間安排車輛路線安排車輛路線安排車輛路線安排問題（車輛路線安排問題（VRP, Vehicle Routing ProblemVRP, Vehicle Routing Problem）是指對(duì)物流配送的車輛進(jìn)行優(yōu)化調(diào)度。該問題一般

55、可以描述如下：對(duì)一系列裝貨點(diǎn)或（和）卸貨點(diǎn)，組織適當(dāng)合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量、數(shù)目限制、車輛行駛里程、時(shí)間限制等）下，達(dá)到一定的目標(biāo)（如最短路程、最小費(fèi)用、最短時(shí)間、最少車輛等）。該問題涉及了多輛交通工具的服務(wù)對(duì)象的選擇和路徑（服務(wù)順序）確定兩方面的問題 VRP問題是組合優(yōu)化領(lǐng)域著名的NP難題之一，求解方法一般相當(dāng)復(fù)雜，通常的做法是應(yīng)用相關(guān)技術(shù)問題分解或者轉(zhuǎn)化為一個(gè)或多個(gè)已經(jīng)研究過的基本問題（如旅行商問題、指派問題、最短路問題等），再使用相對(duì)比較成熟的基本理論和方法進(jìn)行求解。運(yùn)用VRP模型對(duì)實(shí)際問題進(jìn)行研究時(shí)，一般

56、需要考慮以下幾個(gè)方面的問題：u（1 1）倉(cāng)庫(kù)）倉(cāng)庫(kù)。倉(cāng)庫(kù)的級(jí)數(shù)，每級(jí)倉(cāng)庫(kù)的數(shù)量、地點(diǎn)和規(guī)模。u（2 2）車輛。）車輛。車輛的型號(hào)和數(shù)量，每種車輛的容積和運(yùn)作費(fèi)用，出發(fā)時(shí)間和返回時(shí)間，司機(jī)休息時(shí)間，最大的里程和時(shí)間限制。u（3 3）時(shí)間窗口。）時(shí)間窗口。由于各處的工作時(shí)間不同，每個(gè)站點(diǎn)每天只允許在特定的時(shí)間內(nèi)取貨和/或送貨。u（4 4）顧客。）顧客。顧客需求，裝載、卸載，所處的地理位置，分離需求，優(yōu)先等級(jí)。u（5 5）道路信息。）道路信息。車流密度，道路交通費(fèi)用，距離或時(shí)間屬性。u（6 6）貨物信息。）貨物信息。貨物的種類多少，兼容性，貨物的保鮮。u（7 7）運(yùn)輸規(guī)章。）運(yùn)輸規(guī)章。工人每天的工作

57、時(shí)間，車輛的周期維護(hù)。u（1 1）安排車輛負(fù)責(zé)相互距離最接近的站點(diǎn)的貨物運(yùn)輸。）安排車輛負(fù)責(zé)相互距離最接近的站點(diǎn)的貨物運(yùn)輸。u（2 2）安排車輛各日途經(jīng)站點(diǎn)時(shí)，應(yīng)注意使站點(diǎn)群更加緊湊。如果一周內(nèi)）安排車輛各日途經(jīng)站點(diǎn)時(shí)，應(yīng)注意使站點(diǎn)群更加緊湊。如果一周內(nèi)各日服務(wù)的站點(diǎn)不同，就應(yīng)該對(duì)一周內(nèi)每天的路線和時(shí)刻表問題分別進(jìn)各日服務(wù)的站點(diǎn)不同，就應(yīng)該對(duì)一周內(nèi)每天的路線和時(shí)刻表問題分別進(jìn)行站點(diǎn)群劃分。各日站點(diǎn)群的劃分應(yīng)避免重疊。行站點(diǎn)群劃分。各日站點(diǎn)群的劃分應(yīng)避免重疊。u（3 3）從距倉(cāng)庫(kù)最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線）從距倉(cāng)庫(kù)最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線u（4 4）卡車的行車路線應(yīng)呈水滴狀。）卡車的行車路線應(yīng)呈水滴狀

58、。u（5 5）盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的。）盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的。u（6 6）取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。）取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。u（7 7）對(duì)過于遙遠(yuǎn)而無法歸入群落的站點(diǎn)，可以采用其它配送方式。）對(duì)過于遙遠(yuǎn)而無法歸入群落的站點(diǎn)，可以采用其它配送方式。u（8 8）避免時(shí)間窗口過短。）避免時(shí)間窗口過短。簡(jiǎn)化的原則：簡(jiǎn)化的原則：q整數(shù)規(guī)劃法（整數(shù)規(guī)劃法（Integer Programming）q啟發(fā)式方法（啟發(fā)式方法（Heuristics）v節(jié)約法（節(jié)約法（Cla

59、rke and Wright Procedure）v兩階段法兩階段法 ETS (Extension of Traveling Salesman Procedure)v掃描法掃描法v考慮返程考慮返程 Backtracking1、整數(shù)規(guī)劃法、整數(shù)規(guī)劃法2、節(jié)約法（、節(jié)約法（Clarke and Wright Procedure） 節(jié)約法的目標(biāo)是使所有車輛的行駛總里程最短，并且為所有站點(diǎn)提供節(jié)約法的目標(biāo)是使所有車輛的行駛總里程最短，并且為所有站點(diǎn)提供服務(wù)的卡車數(shù)量最少。該方法先假設(shè)每一個(gè)站點(diǎn)都有一輛虛擬的車輛服務(wù)的卡車數(shù)量最少。該方法先假設(shè)每一個(gè)站點(diǎn)都有一輛虛擬的車輛提供服務(wù)，隨后返回倉(cāng)庫(kù)，如圖提供

60、服務(wù)，隨后返回倉(cāng)庫(kù)，如圖(a)所示，這時(shí)的路線里程最長(zhǎng)。下所示，這時(shí)的路線里程最長(zhǎng)。下一步，將兩個(gè)站點(diǎn)合并到同一條行車路線上，減少一輛運(yùn)輸車，相應(yīng)一步，將兩個(gè)站點(diǎn)合并到同一條行車路線上，減少一輛運(yùn)輸車，相應(yīng)地縮短路線里程，選擇節(jié)約距離最多的一對(duì)站點(diǎn)合并在一起，修訂后地縮短路線里程，選擇節(jié)約距離最多的一對(duì)站點(diǎn)合并在一起，修訂后的路線如圖的路線如圖(b)。d0,AdA,0d0,BdB,0ABO倉(cāng)倉(cāng)庫(kù)庫(kù)dA,Bd0,AdB,0a) a) 初始路線初始路線里程里程=d=dO,AO,A+d+dA,OA,O+d+dO,BO,B+d+dB,OB,Ob) b) 兩個(gè)站點(diǎn)合并后的路線兩個(gè)站點(diǎn)合并后的路線里程里程