張靜

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

關(guān)鍵詞：整數(shù)規(guī)劃 配載優(yōu)化 啟發(fā)式算法 Lingo220 Visual C++

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

（一）整數(shù)規(guī)劃模型

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

（二）基于乘用車和轎運車規(guī)格數(shù)據(jù)的相關(guān)分析

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

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）因Ⅰ、Ⅱ、Ⅲ車型的乘用車數(shù)量限制，滿足關(guān)系有： Z11+Z12=156；Z12+Z22=102；Z13+Z23=39；

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

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

實驗結(jié)果：通過Lingo220軟件求解，得到如圖1數(shù)據(jù)：

如圖1所示，最優(yōu)解的車輛數(shù)是30臺，其中1-1型轎運車25臺，1-2型轎運車5臺。相應(yīng)分配方案如下：

（三）用Visual Studio C++建立的配載優(yōu)化模型分析

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

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

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

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

（2）考慮相鄰乘用車之間縱向及橫向的安全車距均至少為01米，可在處理每個乘用車時，假定自身長度都增加01米，則I、II、III型乘用車的長度都變?yōu)?61米、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輛，滿足關(guān)系如下：

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

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

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

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

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

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

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

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

（四）設(shè)計求解線性規(guī)劃的優(yōu)化模型及通用算法

首先對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型，當不足一輛車時不分配。最后再對剩余的車進行微調(diào)。利用Microsoft visual C++軟件，給出通用算法，編寫exe程序，程序是在dos環(huán)境下運行的，具體使用說明如下：

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

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

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

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

（五）結(jié)論

本文研究的主要結(jié)論：

（1）實現(xiàn)了面向轎運車的最大運能優(yōu)化研究。利用整數(shù)規(guī)劃算法，通過對規(guī)劃對象的動態(tài)規(guī)劃變化來調(diào)整計算的速度和精度，優(yōu)化出每輛轎運車針對不同種類乘用車的最大運能配載方案。

（2）實現(xiàn)了面向混裝訂單的配載優(yōu)化的研究。

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

參考文獻：

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

[2]姚婷.車輛調(diào)度遺傳算法[D].西北大學(xué)，2013.

[3]陳賽虎.基于整數(shù)規(guī)劃的轎車物流配載優(yōu)化的研究[D].上海交通大學(xué)，2008.

[4]陳萍.啟發(fā)式算法及其在車輛路徑問題中的應(yīng)用[D].北京交通大學(xué)，2009.

責(zé)任編輯：于蕾endprint