乘用車物流運輸計劃問題的研究

張靜

摘要：本文針對乘用車物流運輸計劃問題，基于現有數據與相關研究，采用整數規劃、配載優化兩種方法，對所需要各種類型轎運車的數量、每輛轎運車的乘用車裝載方案建立了數學模型，從而對整車物流的運輸成本進行定量分析，降低運輸成本。

關鍵詞：整數規劃 配載優化 啟發式算法 Lingo220 Visual C++

中圖分類號：F426文獻標識碼：A文章編號：1009-5349（2017）20-0021-02

（一）整數規劃模型

整數規劃是從1958年由RE戈莫里提出割平面法之后形成獨立分支的，現已發展出很多方法解決各種問題。解整數規劃最典型的做法是逐步生成一個相關的問題，稱它是原問題的衍生問題。對于給定Ⅰ車型、Ⅱ車型、Ⅲ車型的數量，求解所需要各種類型轎運車的數量、每輛轎運車的乘用車裝載方案，顯然可以歸結為啟發式算法中的整數規劃問題。可以應用已有的不同類型轎運車和不同類型乘用車之間的約束條件和目標函數，有效地利用lingo軟件進行整數規劃模型求取可行解，從而得以獲取對所需要各種類型轎運車的數量、每輛轎運車的乘用車裝載方案。

（二）基于乘用車和轎運車規格數據的相關分析

裝載具體要求如下：每種轎運車上、下層裝載區域均可等價看成長方形，各列乘用車均縱向擺放，相鄰乘用車之間縱向及橫向的安全車距均至少為01米，下層力爭裝滿，上層兩列力求對稱，以保證轎運車行駛平穩。受層高限制，高度超過17米的乘用車只能裝在1-1、1-2型下層。假設運輸Ⅰ車型的乘用車156輛、Ⅱ車型的乘用車102輛及Ⅲ車型的乘用車39輛，這里以所有1-1型轎運車和1-2型轎運車的總數量為優化目標如下：

min Z=P1+P2

約束條件為：

（1）由每次1-2型轎運車使用量不超過1-1型轎運車使用量的20%，有P1≤P2；

（2）1-1型和1-2型轎運車裝滿I、II型乘用車的約束：

471*Z11+3715*Z12+473*Z13≤38*P1；

471*Z21+3715*Z22+473*Z23≤729*P2；

（3）因Ⅰ、Ⅱ、Ⅲ車型的乘用車數量限制，滿足關系有： Z11+Z12=156；Z12+Z22=102；Z13+Z23=39；

（4）考慮III型乘用車只能放在轎運車下層的情況，需要滿足放在1-1和1-2型轎運車上的所有乘用車的數量不超過III型車放滿一層1-1和1-2型轎運車時對應的數量限制為： Z13≤P1；Z23≤5*P2；

符號說明：Pi表示所有1-i型轎運車的數量；Zij表示所有1-i型轎運車搭載的乘用車j的數量。

實驗結果：通過Lingo220軟件求解，得到如圖1數據：

如圖1所示，最優解的車輛數是30臺，其中1-1型轎運車25臺，1-2型轎運車5臺。相應分配方案如下：

（三）用Visual Studio C++建立的配載優化模型分析

應用Visual Studio C++軟件，提供一個通用的程序，生成exe的文件，對不同車型的轎運車和同一轎運車上不同乘用車的組合形式進行比例劃分，提高組合利用率和計算效率。在通用程序中可直接在輸入三種乘用車型數量后，迅速得出1-1和1-2所需數量和每種轎運車的搭載組合情況。

面對混裝配載訂單的情況時，不僅需要考慮單輛轎運車中的商品車的配載優化問題，還需要考慮多輛轎運車配載多輛商品車的優化組合問題。用visual C++語言設計求解線性規劃的單純形法，需要從配載優化理論的最基本原理和基本原則出發，進行專門的底層開發，給出通用算法及程序。

BisChoff&Marriott算法是建立在分層的基礎上進行討論的，運用二維填裝技術來解決三維布局問題。該算法的構想是，先按照某種標準確定物體的優先級，然后取出級別高的物體，分別嘗試用它的長、寬、高充當層的寬度，一旦層的厚度確定，由于同層的物體尺寸相同，問題就轉化為二維填裝問題。該算法的特點是要求每一層盡可能由同一類物體組成。如果沒有足夠的尺寸相同的物體能夠把一層裝滿，就暫且放棄對這種物體的處理，轉而處理下一個優先級類別的物體。到最后所有的物體剛好裝入集裝箱內，但是更多的情況是剩下的每類物體都不能裝滿一個完全層。在B&M算法的基礎上，本文對算法思想又做了如下改進：

（1）因為受層高限制，高度超過17米的乘用車只能裝在1-1、1-2型下層，所以III型乘用車只能放在1-1，1-2型轎運車下層中。

（2）考慮相鄰乘用車之間縱向及橫向的安全車距均至少為01米，可在處理每個乘用車時，假定自身長度都增加01米，則I、II、III型乘用車的長度都變為461米、3715米、463米，所以1-1型和1-2型轎運車裝滿I、II型乘用車的條件：

461*Z11+3715*Z12+463*Z13≤38*P1；

461*Z21+3715*Z22+463*Z23≤729*P2；

（3）因Ⅰ車型的乘用車P1輛、Ⅱ車型的乘用車P2輛及Ⅲ車型的乘用車P3輛，滿足關系如下：

Z11+Z21=P1；Z21+Z22=P2；Z13+Z23=P3；

（4）考慮III型乘用車只能放在轎運車下層的情況，需要滿足放在1-1和1-2型轎運車上的所有乘用車的數量不超過III型車放滿一層1-1和1-2型轎運車時對應的最多的數量限制，即：

Z13≤5*P1；Z23≤5*P2；

（5）考慮到使用轎運車的數量能盡量少，算法采用先裝滿I型乘用車，后先裝滿II型乘用車的原則。

（6）算法中優先考慮Ⅰ型和II型乘用車，最后考慮III型乘用車，即III型乘用車的優先級低一些。endprint

（7）在1-1型轎運車中，因為Ⅰ型乘用車最多放4輛，II型乘用車最多放5輛，所以II型乘用車數量大致是Ⅰ型乘用車數量的，這樣分配時可以粗略考慮。

（8）在1-2型轎運車中，按照Ⅰ型乘用車與II型乘用車的比值是1：2，Ⅰ型乘用車與I型乘用車的比值也是1：2來裝載乘用車，這樣就可以更好地節省空間。

（9）在分配裝載乘用車的時候，首先得到次優解，算法會通過優化的過程得到最優解。

（四）設計求解線性規劃的優化模型及通用算法

首先對III型車進行分配，1-1型和1-2型盡量按5比1分配，不足5比1安排1-1型，當III型不足一輛車時不分配，再用I型，II型填充上層空位，其中1-2型轎運車，I型，II型盡可能按1比2排放。再對剩余的I型，II型車進行分配，其中1-1型和1-2型也盡量按5比1分配，不足5比1安排1-1型，當不足一輛車時不分配。最后再對剩余的車進行微調。利用Microsoft visual C++軟件，給出通用算法，編寫exe程序，程序是在dos環境下運行的，具體使用說明如下：

首先打開Testexe，若從文件中讀取請輸入1，手動輸入請輸入2。輸入2后，會自動彈出“請輸入I型車的數量”，輸入I型車的數量后，會自動彈出“請輸入II型車的數量”，輸入II型車的數量后，會自動彈出“請輸入III型車的數量”，輸入III型車的數量后，會顯示各類轎運車各層需要擺放的乘用車的數量。

用Mirosoft visual C++編寫的Testexe程序及給出的通用算法，對各類型轎運車的上下兩層都給出了詳細的裝載方案。一方面實現了面向轎運車的最大運能優化研究。利用整數規劃算法，通過對規劃對象的動態規劃變化來優化出每輛轎運車針對不同種類商品車的最大運能配載方案。另一方面，提供了可行Microsoft visual C++算法分析，實現了面向混裝訂單的配載優化的研究，調整了計算的速度和精度。

運行Testexe，手動輸入各類型乘用車數量要求，得到以下顯示（如圖2）：

對比Lingo220和Microsoft visual C++得到的解，兩種分配方案均能達到配送目的要求，但是對比成本而言，考慮1-2型轎運車成本較1-1型成本高，所以Microsoft visual C++得到的解更優一些。之所以Lingo會出現這樣的結果，并不是模型本身的漏洞，而是Lingo在求解整數規劃的問題上，只會給出一個最優解，而往往問題是會有可能出現多種最優解的情況，卻無法顯示。又因優化目標并沒有考慮到兩種車型的成本，所以，Lingo出現的結果還需要進一步分析，這也體現出了Microsoft visual C++模型的優越性。而且，后者可以清晰地列舉出每種車型的裝配方案，也彌補了整數規劃結果細節上的不足。

（五）結論

本文研究的主要結論：

（1）實現了面向轎運車的最大運能優化研究。利用整數規劃算法，通過對規劃對象的動態規劃變化來調整計算的速度和精度，優化出每輛轎運車針對不同種類乘用車的最大運能配載方案。

（2）實現了面向混裝訂單的配載優化的研究。

（3）提供了所需要各種類型轎運車的數量、每輛轎運車的乘用車裝載方案，設計了一個通用算法。考慮多路徑的乘用車和轎運車分配比例情況，以分配路程為優先級，乘車利用率高為原則建立了一個一般的優化規劃模型，提供了可行Microsoft visual C++算法分析，實現了面向混裝訂單的配載優化的研究，調整計算的速度和精度，具有一定的實際意義。

參考文獻：

[1]蔡菂迪.改進遺傳算法在車輛路徑問題中的研究應用[D].哈爾濱工程大學，2013.

[2]姚婷.車輛調度遺傳算法[D].西北大學，2013.

[3]陳賽虎.基于整數規劃的轎車物流配載優化的研究[D].上海交通大學，2008.

[4]陳萍.啟發式算法及其在車輛路徑問題中的應用[D].北京交通大學，2009.

責任編輯：于蕾endprint