張靜

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

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

中圖分類(lèi)號(hào)：F426文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-5349（2017）20-0021-02

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

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

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

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

min Z=P1+P2

約束條件為：

（1）由每次1-2型轎運(yùn)車(chē)使用量不超過(guò)1-1型轎運(yùn)車(chē)使用量的20%，有P1≤P2；

（2）1-1型和1-2型轎運(yùn)車(chē)裝滿(mǎn)I、II型乘用車(chē)的約束：

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

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

（3）因Ⅰ、Ⅱ、Ⅲ車(chē)型的乘用車(chē)數(shù)量限制，滿(mǎn)足關(guān)系有： Z11+Z12=156；Z12+Z22=102；Z13+Z23=39；

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

符號(hào)說(shuō)明：Pi表示所有1-i型轎運(yùn)車(chē)的數(shù)量；Zij表示所有1-i型轎運(yùn)車(chē)搭載的乘用車(chē)j的數(shù)量。

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

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

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

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

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

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

（1）因?yàn)槭軐痈呦拗疲叨瘸^(guò)17米的乘用車(chē)只能裝在1-1、1-2型下層，所以III型乘用車(chē)只能放在1-1，1-2型轎運(yùn)車(chē)下層中。

（2）考慮相鄰乘用車(chē)之間縱向及橫向的安全車(chē)距均至少為01米，可在處理每個(gè)乘用車(chē)時(shí)，假定自身長(zhǎng)度都增加01米，則I、II、III型乘用車(chē)的長(zhǎng)度都變?yōu)?61米、3715米、463米，所以1-1型和1-2型轎運(yùn)車(chē)裝滿(mǎn)I、II型乘用車(chē)的條件：

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

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

（3）因Ⅰ車(chē)型的乘用車(chē)P1輛、Ⅱ車(chē)型的乘用車(chē)P2輛及Ⅲ車(chē)型的乘用車(chē)P3輛，滿(mǎn)足關(guān)系如下：

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

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

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

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

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

（7）在1-1型轎運(yùn)車(chē)中，因?yàn)棰裥统擞密?chē)最多放4輛，II型乘用車(chē)最多放5輛，所以II型乘用車(chē)數(shù)量大致是Ⅰ型乘用車(chē)數(shù)量的，這樣分配時(shí)可以粗略考慮。

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

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

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

首先對(duì)III型車(chē)進(jìn)行分配，1-1型和1-2型盡量按5比1分配，不足5比1安排1-1型，當(dāng)III型不足一輛車(chē)時(shí)不分配，再用I型，II型填充上層空位，其中1-2型轎運(yùn)車(chē)，I型，II型盡可能按1比2排放。再對(duì)剩余的I型，II型車(chē)進(jìn)行分配，其中1-1型和1-2型也盡量按5比1分配，不足5比1安排1-1型，當(dāng)不足一輛車(chē)時(shí)不分配。最后再對(duì)剩余的車(chē)進(jìn)行微調(diào)。利用Microsoft visual C++軟件，給出通用算法，編寫(xiě)exe程序，程序是在dos環(huán)境下運(yùn)行的，具體使用說(shuō)明如下：

首先打開(kāi)Testexe，若從文件中讀取請(qǐng)輸入1，手動(dòng)輸入請(qǐng)輸入2。輸入2后，會(huì)自動(dòng)彈出“請(qǐng)輸入I型車(chē)的數(shù)量”，輸入I型車(chē)的數(shù)量后，會(huì)自動(dòng)彈出“請(qǐng)輸入II型車(chē)的數(shù)量”，輸入II型車(chē)的數(shù)量后，會(huì)自動(dòng)彈出“請(qǐng)輸入III型車(chē)的數(shù)量”，輸入III型車(chē)的數(shù)量后，會(huì)顯示各類(lèi)轎運(yùn)車(chē)各層需要擺放的乘用車(chē)的數(shù)量。

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

運(yùn)行Testexe，手動(dòng)輸入各類(lèi)型乘用車(chē)數(shù)量要求，得到以下顯示（如圖2）：

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

（五）結(jié)論

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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