何明宇

摘要：配送運(yùn)輸由于目標(biāo)客戶多，一般城市交通路線又較復(fù)雜，如何安排最佳配送路線是非常有挑戰(zhàn)性的一項(xiàng)工作，配送路徑優(yōu)化的基本問題往往可以簡化為旅行商問題。本文的目的是展示如何在MS Excel中使用VLOOKUP和INDEX函數(shù)，結(jié)合“規(guī)劃求解”工具中的Alldifferent約束建立旅行商問題型的配送路徑優(yōu)化求解模型的一種方法，并用實(shí)例說明了方法的操作過程及有效性。

Abstract： ?Due to the large number of target customers and the complicated urban traffic routes， how to arrange the best delivery route is a very challenging task. The basic problems of distribution route optimization can often be simplified to the traveling salesman problem. The purpose of this paper is to show a method to use the VLOOKUP and INDEX functions in MS Excel to establish a traveling salesman problem-based distribution path optimization solution model by combining the Alldifferent constraint in the "Solver" tool， and illustrate the operation and effectiveness of the method with examples.

關(guān)鍵詞：配送;旅行商問題;Alldifferent

Key words： distribution;traveling salesman problem;Alldifferent

中圖分類號(hào)：F253.9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)：1006-4311（2019）27-0216-03

0 ?引言

王之泰教授從資源配置的角度定義“配送是以現(xiàn)代送貨形式實(shí)現(xiàn)資源的最終配置的經(jīng)濟(jì)活動(dòng)。”這一定義認(rèn)為是配送的主要經(jīng)濟(jì)活動(dòng)是以現(xiàn)代生產(chǎn)力、勞動(dòng)手段支撐的，依靠科技進(jìn)步的，使“配”和“送”有機(jī)結(jié)合的一種送貨方式。

在配送過程中，由于配送客戶多，城市交通道路縱橫交錯(cuò)，相當(dāng)復(fù)雜，配送路線安排是否得當(dāng)，不僅影響物流成本和車輛的運(yùn)行時(shí)間，還與城市交通壓力息息相關(guān)。以往配送員大抵是依據(jù)經(jīng)驗(yàn)和城市布局安排的配送路線，缺乏系統(tǒng)的科學(xué)理論和技術(shù)指導(dǎo)，配送效率和經(jīng)濟(jì)性都還有非常大的提升空間。

城市配送的基本問題可以簡化為一輛車從一個(gè)配送中心出發(fā)為若干需求點(diǎn)的客戶送貨，在現(xiàn)有的城市路網(wǎng)中，選擇合適的線路，安排一個(gè)最恰當(dāng)?shù)捻樞蛲瓿伤锌蛻舻乃拓洠瑥亩_(dá)到既能按時(shí)完成任務(wù)，同時(shí)總成本最小，因此配送路徑優(yōu)化的基本問題又可以簡化為旅行商問題。

1 ?旅行商問題（Traveling salesman problem，TSP）

旅行商問題（TSP）是運(yùn)籌學(xué)領(lǐng)域的一道經(jīng)典名題。其一般描述為：有一名旅行推銷商人，從某個(gè)城市出發(fā)，要訪遍若干城市各一次且僅一次，最后返回到原出發(fā)城市，已知從城市i到j(luò)的旅費(fèi)為Cij，問這名旅行推銷商人應(yīng)該如何安排旅行路線使總旅費(fèi)最少？

2 ?TSP模型的數(shù)學(xué)描述

若僅考慮前三個(gè)約束條件簇，則是類似于指派問題的模型。對(duì)TSP模型只是必要條件，并不是充分。例如，六個(gè)城市的旅行路線若為2-1-6-2和5-4-3-5，則該路線雖然滿足前三個(gè)約束條件，但是不構(gòu)成整體巡回路線，它含有兩個(gè)子巡回，因此需要增加“不含子巡回”的約束條件。

3 ?文獻(xiàn)綜述

TSP模型是一個(gè)重要的組合優(yōu)化問題，屬于NP-完全問題。迄今為止，仍然沒有找到求解它的多項(xiàng)式時(shí)間算法，文獻(xiàn)[1，2]認(rèn)為，TSP不能用精確算法得到最優(yōu)解，甚至得到其近似解也是不容易的。

縱觀近幾年的研究成果，研究人員解決TSP的研究方法可以歸為以下幾類，如圖1所示。

這些解法都需要在專門的軟件平臺(tái)中編程，對(duì)一般管理人員來講有一定的難度，文獻(xiàn)[3]基于TSP的混合整數(shù)規(guī)劃模型，并用EXCEL軟件來求解，該方法的優(yōu)點(diǎn)是不需要專門的商業(yè)軟件和高深的編程知識(shí)，但是為了避免形成子回路引入虛擬變量ui，uj構(gòu)建約束條件簇：ui-uj+nxijn-1（1i≠jn），ui，uj為常數(shù)（i，j=1，…，n）。一方面，對(duì)于大多數(shù)人來說都難以理解它的數(shù)學(xué)原理。另外，在建模時(shí)，這一約束條件也不容易被表示，且隨著模型節(jié)點(diǎn)數(shù)的增加，約束條件數(shù)增加非?？欤蟠笤黾幽Ｐ偷膹?fù)雜度。

本文的目的是展示如何在MS Excel中應(yīng)用VLOOKUP和INDEX函數(shù)，結(jié)合規(guī)劃求解工具中的Alldifferent約束建立旅行商問題（TSP）的模型并求出最優(yōu)解，該方法的實(shí)際意義是可以為目前城市配送路線的優(yōu)化問題提供一種快速有效的求解方法。

4 ?利用Excel求解器優(yōu)化城市配送路徑

案例：HQ便利連鎖超市是四川省內(nèi)的一家A股上市公司。公司現(xiàn)建有三座配送中心，為全市2900家連鎖超市統(tǒng)一配送貨物。根據(jù)門店需求信息，第三配送中心DC3需要安排一輛車為周邊14家門店進(jìn)行補(bǔ)貨，DC3與14家門店的距離矩陣如圖2所示，如何設(shè)計(jì)配送路線才能使得車輛從配送中心DC3出發(fā)，配送完畢后返回到DC3所經(jīng)過的路程最短？

4.1 EXCEL建模知識(shí)準(zhǔn)備

4.1.1 VLOOKUP

VLOOKUP 是 Excel 中最常用且最有用的函數(shù)之一，用于在表格或區(qū)域中按行查找項(xiàng)目。VLOOKUP 的語法如下：

VLOOKUP（lookup_value，table_array，col_index_num，[range_lookup]）

其中：

lookup_value：必需。查閱值;

table_array：必需。包含查閱值的區(qū)域;

col_index_num：必需。包含返回值的區(qū)域中的列號(hào);

range_lookup：可選。TRUE為近似匹配，F(xiàn)ALSE為精確匹配。

4.1.2 INDEX

INDEX 函數(shù)返回表格或區(qū)域中的值或值的引用。使用 INDEX函數(shù)有兩種方法：數(shù)組形式和引用形式。本文的模型需要返回指定單元格或單元格數(shù)組的值，故選用數(shù)組形式。其語法如下：

INDEX（array， row_num， [column_num]）

其中：

array：必需。單元格區(qū)域或數(shù)組常量;

row_num：必需。選擇數(shù)組中的某行，函數(shù)從該行返回?cái)?shù)值;

column_num：可選。選擇數(shù)組中的某列，函數(shù)從該列返回?cái)?shù)值。

4.1.3 Alldifferent

一種特殊類型的整數(shù)約束（稱為“不同”約束），其中n個(gè)決策變量的值必須是從1到n的整數(shù)排列。主要應(yīng)用于涉及確定最佳排序類問題。

4.2 建立配送路徑優(yōu)化的EXCEL模型，如圖3所示

步驟1：對(duì)配送中心及門店進(jìn)行順序編號(hào)，即D3：R3，B5：B19區(qū)域中的數(shù)字。輸入配送中心DC3與14家門店的距離矩陣。

步驟2：確定決策變量和初始可行解。

從配送中心DC出發(fā)，因?yàn)榭尚械拇涡蚨家笠L遍所有門店各一次且僅一次，最后返回原出發(fā)地，因此，我們選擇編號(hào)為0的配送中心DC作為起點(diǎn)。

C23：C36區(qū)域?yàn)闆Q策變量，顯示途中的旅程，以數(shù)字的次序?qū)ε渌椭行暮烷T店進(jìn)行排序。當(dāng)我們抵達(dá)第n-1個(gè)節(jié)點(diǎn)時(shí)，必須要回到編號(hào)為0的配送中心，所以單元格C37并不是決策變量。

我們設(shè)單元格B23為0，無論你選擇那一家門店，從編號(hào)為0的配送中心到它之間的距離就是C23中的變量，由于要確保這家門店變成下一行程中的“起始”門店，所以在單元格B24中設(shè)置公式“=C23”，向下復(fù)制填充至B37單元格。

步驟3：建立目標(biāo)函數(shù)。

在單元格D23中輸入公式“=INDEX（$D$5：$R$19，B23+1，C23+1）”，該公式的目的是從距離表中查詢出從一個(gè)節(jié)點(diǎn)i出發(fā)去到另一節(jié)點(diǎn)j走過的路程，然后向下復(fù)制填充至D37單元格。

在單元格D38中輸入公式“=SUM（D14：D19）”，用于計(jì)算走完全部門店后回到配送中心的總路程，它將作為規(guī)劃求解的目標(biāo)單元格。

步驟4：將這些節(jié)點(diǎn)編號(hào)的數(shù)值轉(zhuǎn)換成配送中心或門店名稱。在單元格F23中輸入公式“=VLOOKUP（B23，$B$5：$C$19，2）”，然后向下復(fù)制填充至單元格F37。在單元格G23中輸入公式“=VLOOKUP（C23，$B$5：$C$19，2）”，然后向下復(fù)制填充至單元格G37。

4.3 設(shè)置規(guī)劃求解參數(shù)

選中D38單元格，點(diǎn)擊數(shù)據(jù)|規(guī)劃求解，打開“規(guī)劃求解參數(shù)”對(duì)話框，在“設(shè)置目標(biāo)”文本框中輸入D38，選中“最小值”單選按鈕，在“可變單元格”文本框中輸入C23：C36。

單擊“添加”按鈕，打開“添加約束”對(duì)話框添加約束條件，本例中所包含的約束條件如下：

條件1：C23：H36=ALLDifferent（不含子巡回）

因?yàn)槟Ｐ蜑榉枪饣?guī)劃求解問題，故求解方法應(yīng)選擇“演化”，規(guī)劃求解參數(shù)全部設(shè)置完畢，如圖4所示。

4.4 求解模型

單擊“規(guī)劃錄解參數(shù)”對(duì)話框中的“求解”按鈕開始求解運(yùn)算。在“規(guī)劃求解結(jié)果”對(duì)話框中并顯示找到一個(gè)最優(yōu)結(jié)果，如圖5所示。

單擊的“確定”按鈕可以保存求出的最優(yōu)結(jié)果，如圖6所示。

通過圖5中的可以看出，求得的最優(yōu)路徑為：DC3→N→K→J→L→I→M→F→A→B→G→C→D→E→H→DC3，配送車輛行駛的總里程為82.68千米。

5 ?結(jié)論

①盡管有許多學(xué)者利用專業(yè)軟件對(duì)旅行商問題建立了較為系統(tǒng)的算法模型，但是，實(shí)際應(yīng)用中經(jīng)常遇到許多問題，如需要專業(yè)軟件環(huán)境支持，軟件費(fèi)用昂貴，操作員專業(yè)化程度要求很高等。

②靈活運(yùn)用Excel結(jié)合其強(qiáng)大計(jì)算能力建立了配送管理中路線優(yōu)化決策中的基本問題——TSP的ECXCEL模型，為該類問題的求解提供了一種有效的思路。該方法在配送和運(yùn)輸物流領(lǐng)域具有重要的實(shí)際意義。

③模型求解花費(fèi)時(shí)間： 89.187 秒。表明使用該模型求解一般的路線優(yōu)化問題快速且高效。需求地的增加成倍地增加了（尋找最佳行走路線）任務(wù)的復(fù)雜性，使用MS Excel 規(guī)劃求解工具可以很容易地解決TSP類型的配送路徑優(yōu)化問題，而不用擔(dān)心客戶的數(shù)量。

參考文獻(xiàn)：

[1]徐麗蕊.城市配送TSP問題的LINGO求解[J].電子設(shè)計(jì)工程，2015，23（13）：62-64.

[2]嚴(yán)晨，王直杰.以TSP為代表的組合優(yōu)化問題研究現(xiàn)狀與展望[J].計(jì)算機(jī)仿真，2007，24（6）：171-174.

[3]張敏，金琴玲.旅行商問題的一種新解法[J].重慶職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2008（1）：153-154.

[4]戴宗瑞.TSP問題在物流配送車輛運(yùn)行路線中的應(yīng)用分析[J].軟件導(dǎo)刊，2012，11（6）：93-95.

[5][美]Michael R.Middleton.使用Microsoft Excel進(jìn)行數(shù)據(jù)分析[M].北京：中國水利水電出版社，1997.

[6]ExcelHome. Excel 2010數(shù)據(jù)處理與分析實(shí)戰(zhàn)技巧精粹[M].北京：人民郵電出版社，2014，1.

[7]王劍文，戴光明，謝柏橋，張全元.求解TSP問題算法綜述[J].計(jì)算機(jī)工程與科學(xué)，2008，30（2）：72-74.

[8]潘正君，康立山，陳毓屏.演化計(jì)算[M].北京：清華大學(xué)出版社，1997.