六、運(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)輸?shù)?/p>

4、主要鐵路是國(guó)民經(jīng)濟(jì)的大動(dòng)脈，鐵路運(yùn)輸是我國(guó)貨物運(yùn)輸?shù)闹饕绞健ｈF路運(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è)施修建成本較高，鐵路設(shè)

6、施修建成本較高，占地多。占地多。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)輸?shù)淖儎?dòng)成本相對(duì)

7、較高，因?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)率低，單位運(yùn)價(jià)勞動(dòng)生

8、產(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)輸工具的裝載量大，單位運(yùn)輸工具的裝載量大

10、，運(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)輸l航空貨運(yùn)的主要優(yōu)點(diǎn)在于

11、運(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ó)家投資，航空公司的固定成本主要與購空港的建設(shè)運(yùn)營(yíng)由國(guó)家投資，航空公司的固定成本主要與購買飛機(jī)有

12、關(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有些貨物禁用空運(yùn)有些貨物禁用空運(yùn) u受天

13、氣影響較大受天氣影響較大 綜合上述優(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)輸速度很慢，還可以將管道作為倉庫。另外，因?yàn)楣艿肋\(yùn)輸速度很慢，還可以將管道作為倉

14、庫。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 34 43 3河運(yùn)河運(yùn)3 34 4

15、3 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)的成本與速度有關(guān)的成本直送v.s中

16、轉(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)輸所需的時(shí)間越短，其效用價(jià)值越高。單位

17、貨物運(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,.,n, the require

18、d 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 equal to the areas b

19、elow 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庫存成本v交易成本運(yùn)輸服務(wù)的選擇運(yùn)輸服務(wù)的選擇q 的影響是決策者心目中的影響是決策者心目中最重要的運(yùn)輸服務(wù)要素，因此，這三項(xiàng)是運(yùn)輸服最重要的運(yùn)輸服務(wù)要素，因此，這三項(xiàng)是運(yùn)輸服務(wù)選擇的基礎(chǔ)。務(wù)選擇的基礎(chǔ)。q

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

21、最小的運(yùn)輸方式。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫存成本據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫存成本可以減少可以減少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ù)的選擇的定量分析法q分析：分析：v以年總成本最低

22、為原則來選擇合適的運(yùn)輸方式。這里，以年總成本最低為原則來選擇合適的運(yùn)輸方式。這里，總成本總成本=運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用+庫存成本；庫存成本；v其中，其中，運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用=運(yùn)輸量運(yùn)輸量 費(fèi)率費(fèi)率v庫存成本庫存成本=在途運(yùn)輸庫存成本在途運(yùn)輸庫存成本+工廠存貨成本工廠存貨成本+倉庫存?zhèn)}庫存貨成本貨成本v在途運(yùn)輸庫存費(fèi)用在途運(yùn)輸庫存費(fèi)用=ICDT/365v工廠存貨成本工廠存貨成本=ICQ/2v倉庫存貨成本倉庫存貨成本=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)量；C產(chǎn)品單價(jià)；產(chǎn)品單價(jià)； I年存

23、貨成本（產(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)輸公路運(yùn)輸 航空運(yùn)輸航空運(yùn)輸 運(yùn)輸成運(yùn)輸

24、成本本 R D 70000105000140000980000在途庫在途庫存存 ICDT/365 345205241644 8630134521工廠存工廠存貨貨 ICQ/2 900000416500378000182250倉庫存?zhèn)}庫存貨貨 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)相同的路徑規(guī)劃vTraveling S

25、alesman 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求解此類最短路徑問題，主要有以下幾種算法：q（1）Dijkstra算法；

26、（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)。找出的最近節(jié)點(diǎn)是終點(diǎn)。（2 2）在前面

27、的迭代過程中找出（）在前面的迭代過程中找出（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)與其候選點(diǎn)之間的距離累加到該已解節(jié)點(diǎn)與起

28、點(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算法使用距離矩陣距離矩陣和路由矩陣路由矩陣。q距離矩

29、陣距離矩陣是一個(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ù)值收斂。按順序，依次作為中間節(jié)點(diǎn)，（按順序，后面的點(diǎn)不作為（按

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

31、143311454223551234R33105615412345131081223115931011610485645129104D4123451232421444314444223554444S42多個(gè)起、止點(diǎn)的路徑規(guī)劃當(dāng)有多個(gè)貨源和多個(gè)目的地時(shí)，就需要指定目的地的供貨地，同時(shí)當(dāng)有多個(gè)貨源和多個(gè)目的地時(shí)，就需要指定目的地的供貨地，同時(shí)要找到供貨地、目的地之間的最佳路徑。要找到供貨地、目的地之間的最佳路徑。例例 某公司下屬三個(gè)倉庫，供應(yīng)四個(gè)客戶的需要，三個(gè)倉庫的供應(yīng)量某公司下屬三個(gè)倉庫，供應(yīng)四個(gè)客戶的需要，三個(gè)倉庫的供應(yīng)量和四個(gè)客戶的需求量，以及由各倉庫到各客戶的運(yùn)輸單價(jià)如下表所示。和四個(gè)客

32、戶的需求量，以及由各倉庫到各客戶的運(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)地倉庫倉庫A311310700倉庫倉庫B1928400倉庫倉庫C74105900需求量需求量3006005006002000表上做業(yè)法表上做業(yè)法，該方法適合于對(duì)相對(duì)簡(jiǎn)單的問題進(jìn)行求解，求解過程方便，該方法適合于對(duì)相對(duì)簡(jiǎn)單的問題進(jìn)行求解，求解過程方便直觀，而且由于計(jì)算量不大，可以用手工直接完成。利用表上作業(yè)法有兩直觀，而且由于計(jì)算量不大，可以用手工直接完成。利用表上作業(yè)法有兩個(gè)基本步驟：個(gè)基本步驟：（1 1）確定初始

33、調(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)地倉庫倉庫A400300700倉庫倉庫B300100400倉庫倉庫C600300900需求量需求量300600500600表表5.4 初始調(diào)運(yùn)方案初始調(diào)運(yùn)方案（2 2）初始方案的檢驗(yàn)）初始方案的檢驗(yàn)最優(yōu)方案的數(shù)字特征最優(yōu)方案的數(shù)字特征檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：閉回路：閉回路： 從理論上講，對(duì)于表上作業(yè)法的

34、初始方案來說，從調(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)；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行（列）若有閉合回路的頂點(diǎn)，則必有兩個(gè)。每一行（列）若有閉合回路的頂點(diǎn)，則必有兩個(gè)。 只

35、有從空格出發(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)地倉庫倉庫A400300700倉庫倉庫B300100400倉庫倉庫C600300900需求量需求量300600500600 表表6.56.5給出了單元格（給出了單元格（1 1，1 1）和（）和（3 3，1 1）所形成的閉回路：（）所形成的

36、閉回路：（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)是增加還是減少。我們把所計(jì)算出來的每條閉回路上調(diào)整單位運(yùn)量而使運(yùn)輸費(fèi)用發(fā)生變化的增減值，稱其為檢

37、驗(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ì)偶變量。在初始調(diào)運(yùn)方案中x13,x14,x21,x23,x32,x34是基變量，這時(shí)對(duì)應(yīng)

38、的檢驗(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 c14-(u1+v4)=0 10-( u1+v4)=0 x34 c34-(u3+v4

39、)=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,在行中填入在行中填入vivi。接著，。接著，按按ij=cij-(ui+vj)ij=cij-(ui+vj

40、)計(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)地倉庫倉庫A12002倉庫倉庫B010-11倉庫倉庫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ù)絕對(duì)出現(xiàn)負(fù)值的檢驗(yàn)數(shù)。如果檢驗(yàn)數(shù)的負(fù)值不止個(gè)時(shí)，一般選擇負(fù)檢驗(yàn)數(shù)絕對(duì)值最大的空格作為

41、具體調(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ù)值作為調(diào)整量。在此將作為調(diào)整量。在此將x x2323單元格的單元格的100100作為

42、調(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)地倉庫倉庫A500200700倉庫倉庫B300100400倉庫倉庫C600300900需求量需求量300600500600表表6.7 6.7 調(diào)整后的方案調(diào)整后的方案按新方案計(jì)算調(diào)運(yùn)物資的運(yùn)輸費(fèi)用為：

43、按新方案計(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ù)值的格子的閉回路 在滿足所有約束條件的情況下，盡可能增大這在滿足所有約束條件的情況下，盡可能增大這個(gè)格子的個(gè)格子的xij值值 調(diào)整此閉回路上其他頂點(diǎn)的值調(diào)整此閉回路上其他頂點(diǎn)

44、的值 檢驗(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è)旅行者從出發(fā)地出發(fā)，經(jīng)過所有要到達(dá)的城市后，返回到出發(fā)一個(gè)旅行者從出發(fā)地出發(fā)，經(jīng)過所有要到達(dá)

45、的城市后，返回到出發(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 allfor 1 , 011ijxNjxNixijiijjijTSPTSP問題求解算法問

46、題求解算法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交換法v綜合型綜合型(composite)合并執(zhí)行路線構(gòu)建及路線改善Assignment

47、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可行解尚未找到?？尚薪馍形凑业健此時(shí)考慮此時(shí)考慮 增加一增加一個(gè)個(gè)“費(fèi)用最小的費(fèi)用最小的非非0路徑路徑” ，看，看看是否有可行解

48、。看是否有可行解。得到：得到：仍然沒有可行解。仍然沒有可行解。此時(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)選擇的路徑，形成新的計(jì)算表；、簡(jiǎn)化計(jì)算表，消除已經(jīng)選擇的路徑，形成新的計(jì)算表；繼續(xù)分支定界。繼續(xù)分支定界

49、。同時(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路徑，得到：路徑，得到：假設(shè)不選擇假設(shè)不選擇E,D路徑：路徑：傳統(tǒng)啟發(fā)式解法傳統(tǒng)啟發(fā)式解法q1、最近鄰點(diǎn)法、最

50、近鄰點(diǎn)法(Nearest-neighbor Heuristic)v 任選一節(jié)點(diǎn)為起點(diǎn)任選一節(jié)點(diǎn)為起點(diǎn)xv 尋找距離節(jié)點(diǎn)尋找距離節(jié)點(diǎn)x最近的節(jié)點(diǎn)最近的節(jié)點(diǎn)y作為下一個(gè)造訪的節(jié)點(diǎn)作為下一個(gè)造訪的節(jié)點(diǎn)v 尋找距離節(jié)點(diǎn)尋找距離節(jié)點(diǎn)y最近的節(jié)點(diǎn)最近的節(jié)點(diǎn)z作為下一個(gè)造訪的節(jié)點(diǎn)作為下一個(gè)造訪的節(jié)點(diǎn)v 重復(fù)以上步驟，直到所有節(jié)點(diǎn)均已造訪重復(fù)以上步驟，直到所有節(jié)點(diǎn)均已造訪1. 連接最后一個(gè)節(jié)點(diǎn)與起點(diǎn)，即形成一個(gè)連接最后一個(gè)節(jié)點(diǎn)與起點(diǎn)，即形成一個(gè)TSP的可行解的可行解1、最近鄰點(diǎn)法、最近鄰點(diǎn)法74387553481234514738247553773443538585482、插入法插入法(Insertion M

51、ethod)(Insertion Method)v 任選一節(jié)點(diǎn)為起點(diǎn)任選一節(jié)點(diǎn)為起點(diǎn)av 尋找距離節(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的子回路的子回路v 尋找距離子回路最近的節(jié)點(diǎn)尋找距離子回路最近的節(jié)點(diǎn)k作為下一個(gè)插入點(diǎn)作為下一個(gè)插入點(diǎn)v 尋找插入成本最小的位置尋找插入成本最小的位置(i-j)，將，將k插入插入i-j之間，形之間，形成新的子回路。成新的子回路。插入成本：插入成本：Cik+Ckj-Cijv 重復(fù)步驟重復(fù)步驟34，直到所有節(jié)點(diǎn)均已插入回路之中，即，直到所有節(jié)點(diǎn)均已插入回路之中，即形成一個(gè)形成一個(gè)TSP的可行解的可行解

52、2、插入法插入法743875534833733774557744888445584543 3、 2-opt 2-opt 交換交換法法q先構(gòu)建一個(gè)起始可行解先構(gòu)建一個(gè)起始可行解q在可行解中任選兩個(gè)不相鄰的節(jié)線在可行解中任選兩個(gè)不相鄰的節(jié)線(a b, c d)，以及另外兩條對(duì)應(yīng)之替換節(jié)線，以及另外兩條對(duì)應(yīng)之替換節(jié)線(a c, b d)，計(jì)算替換后總成本是否降低，計(jì)算替換后總成本是否降低 (即檢查即檢查替換成本是否小于替換成本是否小于0)。 替換成本：替換成本：Cac+Cbd-Cab-Ccd (對(duì)稱型對(duì)稱型TSP)q若替換后總成本有降低，則予以替換，同時(shí)若替換后總成本有降低，則予以替換，同時(shí)變更中間

53、相關(guān)弧線的行走方向變更中間相關(guān)弧線的行走方向q重復(fù)步驟重復(fù)步驟23，直到所有可能的替換均無法，直到所有可能的替換均無法再降低成本為止再降低成本為止3 3、 2-opt 2-opt 交換交換法法74387553484 4、常見的宏啟發(fā)式方法、常見的宏啟發(fā)式方法(Meta-heuristics)(Meta-heuristics)v禁忌搜索法禁忌搜索法(Tabu Search, TS)v基因算法基因算法(Genetic Algorithm, GA)v模擬退火法模擬退火法(Simulated Annealing, SA)v門限值接受法門限值接受法(Threshold Accepting, TA)v神經(jīng)

54、網(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)度。該問題一般可以描述如下：對(duì)一系列裝貨點(diǎn)或（和）卸貨點(diǎn)，組織適當(dāng)合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量、數(shù)目限制、車輛行駛里程、時(shí)間限制等）下，

55、達(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í)，一般需要考慮以下幾個(gè)方面的問題：u（1 1）倉庫）倉庫。倉庫的級(jí)數(shù)，每級(jí)倉庫的數(shù)量、地點(diǎn)和規(guī)模。u（2 2）車輛。）車輛。車輛的型號(hào)和數(shù)量，每種車輛的容積和運(yùn)作費(fèi)用，出發(fā)時(shí)間和返回時(shí)間，司機(jī)休息時(shí)間，最

56、大的里程和時(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ī)章。工人每天的工作時(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)）安

57、排車輛各日途經(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）從距倉庫最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線）從距倉庫最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線u（4 4）卡車的行車路線應(yīng)呈水滴狀。）卡車的行車路線應(yīng)呈水滴狀。u（5 5）盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的。）盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的。u（6 6）取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再

58、取貨。）取貨、送貨應(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é)約法（Clarke and Wright Procedure）v兩階段法兩階段法 ETS (Extension of Traveling Salesman Procedure)v掃描法掃描法v考慮返程考慮返程

59、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ù)，隨后返回倉庫，如圖提供服務(wù)，隨后返回倉庫，如圖(a)所示，這時(shí)的路線里程最長(zhǎng)。下所示，這時(shí)的路線里程最長(zhǎng)。下一步，將兩個(gè)站點(diǎn)合并到同一條行車路線上，減少一輛運(yùn)輸車，相應(yīng)一步，將兩個(gè)站點(diǎn)合并到同一條行車路線上，減少一輛運(yùn)輸

60、車，相應(yīng)地縮短路線里程，選擇節(jié)約距離最多的一對(duì)站點(diǎn)合并在一起，修訂后地縮短路線里程，選擇節(jié)約距離最多的一對(duì)站點(diǎn)合并在一起，修訂后的路線如圖的路線如圖(b)。d0,AdA,0d0,BdB,0ABO倉倉庫庫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)合并后的路線里程里程=d=dO,AO,A+d+dA,BA,B+d+dB,OB,O 節(jié)約里程：節(jié)約里程：dA,O+dB,O-dA,B例：例：1 1、按距離中心的距離，從小到大排序、按距離中心的距離，從小到大排序2 2、計(jì)