這是網(wǎng)絡上出現(xiàn)的關于貨運公司的運輸問題討論，是目前高校物流專業(yè)畢業(yè)論文話題，內(nèi)容涉及廣泛，線性規(guī)劃模型、減小運輸成本考量……等等，下面是針對該問題的詳細解決方案。

1 摘要

本文根據(jù)貨運公司需要完成的運輸量和確定的運輸路線圖，對貨運公司的出車調(diào)度方案進行分析和優(yōu)化，分別建立了線性規(guī)劃模型和0-1規(guī)劃模型，解決了車輛安排問題，得出了運費最小的調(diào)度方案。

首先，由于每次出車的出車成本費是固定的，為了減小運輸成本，就要減少出車次數(shù)，但同時又要滿足各公司對材料的需求，以公司需求為約束條件，以最小出車數(shù)為目標函數(shù)，建立一個線性規(guī)劃模型，并用Lingo求解，得出了最少出車次數(shù)為27輛。進一步考慮運輸車調(diào)度問題，由于出車方向不定，分為逆時針和順時針兩種情況，而且這兩種情況是非此即彼的對立關系，故建立了一個0-1規(guī)劃模型，0表示順時針行駛，1表示逆時針行駛，采用Lingo求解，得出了運輸車在運輸途中不允許掉頭的調(diào)度方案（見表一）。

問題二中允許運輸車掉頭只會影響運輸車卸貨后空載的行駛路程，也即運輸車的空載費用，故通過修改目標函數(shù)中的相關系數(shù)，仍然建立線性規(guī)劃模型和0-1規(guī)劃模型，采用Lingo求解，得出需要安排的運輸車為3輛，運輸途中允許掉頭的調(diào)度方案見表二。

問題三中增加了運輸車的種類，并區(qū)分了運輸車空載時的運費，由于運輸車裝載材料的方式有很多種，在上面分析的基礎上，增加約束條件，得出一種新的線性規(guī)劃模型，通過Lingo解得需要安排的車輛數(shù)為5輛，調(diào)度方案見表三。第（2）小問中，考慮部分公司有道路相通，采用Dijkstra算法來解決這類最短路問題。

關鍵字：線性規(guī)劃模型，0-1規(guī)劃模型，Dijkstra算法

2 問題重述

某地區(qū)有8個公司（如圖一編號①至⑧），某天某貨運公司要派車將各公司所需的三種原材料A,B,C從某港口（編號⑨）分別運往各個公司。路線是唯一的雙向道路（如圖一）。貨運公司現(xiàn)有一種載重 6噸的運輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次（車輛每出動一次為一車次）。每輛車平均需要用15分鐘的時間裝車，到每個公司卸車時間平均為10分鐘，運輸車平均速度為60公里／小時（不考慮塞車現(xiàn)象），每日工作不超過8小時。運輸車載重運費1.8元/噸公里，運輸車空載費用0.4元/公里。一個單位的原材料A,B,C分別毛重4噸、3噸、1噸，原材料不能拆分，為了安全，大小件同車時必須小件在上，大件在下。卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當天的需求量（見圖二）。

問題：1.貨運公司派出運輸車6輛，每輛車從港口出發(fā)（不定方向）后運輸途中不允許掉頭，應如何調(diào)度（每輛車的運載方案，運輸成本）使得運費最小。

2. 每輛車在運輸途中可隨時掉頭，若要使得成本最小，貨運公司怎么安排車輛數(shù)？應如何調(diào)度？

3.（1）如果有載重量為4噸、6噸、8噸三種運輸車，載重運費都是1.8元/噸公里，空載費用分別為0.2，0.4，0.7元/公里，其他費用一樣，又如何安排車輛數(shù)和調(diào)度方案？

（2）當各個公司間都有或者部分有道路直接相通時，分析運輸調(diào)度的難度所在，給出你的解決問題的想法（可結(jié)合實際情況深入分析）。

（圖 一）唯一的運輸路線圖和里程數(shù)

（圖 二）各個公司對每種材料的需求量（單位/天）

3 模型假設

1．假設每輛車裝載時發(fā)揮其最大的裝載能力；

2．假設貨運公司都是先考慮節(jié)省人力和出車次數(shù)最少的情況下再考慮如何安排運輸方式以減少經(jīng)費支出；

3．假設運輸車行駛過程中不考慮塞車拋錨現(xiàn)象，以保證每輛車每天可以達到最大的作業(yè)時間。

4 符號說明

C1? 一單位A材料和二單位C材料的裝載方式；

C2? 二單位B材料的裝載方式；

C3? 六單位C材料的裝載方式；

C4? 一單位B材料和三單位C材料的裝載方式；

Pij 被調(diào)用車的運輸經(jīng)費；

Sij 所運載的區(qū)間的路程；

Xij 第i輛列車的調(diào)度情況；

Xi0=1表示第i輛車采用順時針運輸；

Xi0=0表示第i輛車不采用順時針運輸；

Xi1=1表示第i輛車采用逆時針運輸；

Xi1=0表示第i輛車不采用順時針運輸；

t0? 裝載時間；

t1? 路途行程時間；

t2? 卸載時間；

Gni（n=1—8，i=1，2，3）表示第n個公司分別對A，B，C產(chǎn)品的需求量；

5 問題分析

對于這個貨運公司的運輸問題，問題一中給出了6輛可以使用的運輸車，根據(jù)各公司對材料的需求，這6輛車必然會被反復的調(diào)用。要減少運輸經(jīng)費，首先要減少出車的次數(shù)，但是究竟要出車幾次才可以滿足公司對材料的需求呢？由于每輛車只能裝載6噸的貨物，所以每輛車的裝載方案有： 6個C，2個B， 1個A 2個C，1個B 3個C四種（每次出車都優(yōu)先考慮發(fā)揮每輛運輸車最大的裝載能力），這樣再根據(jù)八個公司對A，B，C三種材料總的需求量就可以建立一個線性規(guī)劃模型求出出車的最少次數(shù)S。在滿足最少出車次數(shù)S的前提下，還要考慮運輸車的調(diào)度問題，由于出車方向不定，分為逆時針和順時針兩種情況，而且這兩種情況是非此即彼的對立關系，這屬于0-1規(guī)劃問題，解決的方法是令Xi0等于1表示采用第i輛車次按順時針來運行，Xi0等于0表示不采用第i輛車次順時針運行。Xi1等于1表示采用第i輛車次逆時針運行，等于0表示不采用這輛車次逆時針運行，再結(jié)合題目中的其他相關數(shù)據(jù)便可以建立一個0-1規(guī)劃模型求解。 問題二中的解決方法和第一問中的解決方法是一樣的，不過由于這時候運輸車可以掉頭，故可以減少由于運輸車在途中空載的路程，而這只會影響模型中目標函數(shù)的中的價值系數(shù)的改變，其他和第一問的求解方法是一致的。在第三問中給出了三種不同的運輸車，對于這三輛不同的運輸車，每次出車時可以用來裝載不同單位的A，B，C材料（這時我們不像第一問那樣來考慮，每次出車可以不裝載完每輛車），對于這三種不同的運輸車可以得出很多不同的裝載方式，比如對于裝載量為8噸的運輸車，可以為每次裝載2個A或者1個A和B等。根據(jù)每個公司對A，B，C不同材料的要求，我們再建立一個線性模型，使得這八個公司可以從這些不同的運輸方式中選擇最為合適的運輸方式的組合以滿足要求，然后對這些公司所選擇的不同的運輸方式再根據(jù)題目中每輛車每天最大的作業(yè)時間，可以確定出在保證完成任務的情形下，所需要不同類型運輸車的最少數(shù)目。這樣就可以減少指派運輸車的支出，然后對不同的運輸車次在途中 的運輸，都考慮其在途中是按最少經(jīng)費的運輸方式來運行（考慮在保證完成了本次出車的任務后，在返回港口中時，是繼續(xù)或掉頭更節(jié)省經(jīng)費），再結(jié)合前面的不同運輸方式的組合，就可以安排出車輛數(shù)和調(diào)度方案了。