許靜慧

摘要：針對(duì)訂單配送中多倉(cāng)庫(kù)多配送任務(wù)的路徑規(guī)劃問(wèn)題，配送路線具有從倉(cāng)庫(kù)取貨出發(fā)，經(jīng)過(guò)多個(gè)配送點(diǎn)完成送貨任務(wù)后返回出發(fā)倉(cāng)庫(kù)的特點(diǎn)。鑒于目前移動(dòng)平臺(tái)上路徑規(guī)劃應(yīng)用主要解決已知起點(diǎn)到終點(diǎn)的路線規(guī)劃，對(duì)于經(jīng)過(guò)多個(gè)沿途點(diǎn)的規(guī)劃尚未有較好的應(yīng)用實(shí)現(xiàn)。因此該文將路徑規(guī)劃與iOS平臺(tái)相結(jié)合充分地利用電子地圖的應(yīng)用特點(diǎn)，設(shè)計(jì)并實(shí)現(xiàn)了基于iOS的訂單配送路徑規(guī)劃系統(tǒng)以便提供給配送員最優(yōu)路徑結(jié)果。重點(diǎn)研究如何利用高德iOS地圖SDK實(shí)現(xiàn)地圖顯示與操作、地圖定位、標(biāo)注繪制、路線規(guī)劃等功能。最后利用進(jìn)銷存管理平臺(tái)的實(shí)際訂單數(shù)據(jù)，測(cè)試證明了該系統(tǒng)的有效性與便捷性。

關(guān)鍵詞：路徑規(guī)劃；多倉(cāng)庫(kù)多配送任務(wù)；iOS；電子地圖；最優(yōu)路徑

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）32-0190-04

Design and Implementation of Order Routing System Based on iOS

XU Jing-hui

（North China University of Technology， Beijing 100144， China）

Abstract： The routing problem of multi-warehouse and multi-distribution task in order distribution has the characteristics of picking from the warehouse and returning to the starting warehouse after completing the delivery task by multiple distribution points. In view of the current path planning applications on the mobile platform to solve the known starting point to the end of the route planning， after a number of points along the planning has not yet been a good application to achieve. Therefore， this paper combines the path planning and iOS platform to make full use of the characteristics of electronic map application， design and implement the order routing system based on iOS in order to provide the optimal path results. This paper focuses on how to realize the function of map display and operation， map location， mark drawing， route planning and so on. Finally， using the real order data of inventory management platform， the test proves the effectiveness and convenience of the system.

Key words： route plan； multi-warehouse multi-distribution tasks； iOS； digital map； optimal path

在實(shí)際訂單配送環(huán)節(jié)中，路徑規(guī)劃要求找出車輛從倉(cāng)庫(kù)取貨出發(fā)依次經(jīng)過(guò)一系列配送點(diǎn)后返回倉(cāng)庫(kù)的最短回路路徑。目前關(guān)于路徑規(guī)劃的研究多數(shù)集中在常見(jiàn)路徑算法的改進(jìn)及優(yōu)化方面[1-3]，對(duì)于路徑規(guī)劃應(yīng)用系統(tǒng)的研究還較少。國(guó)內(nèi)iOS平臺(tái)上有關(guān)路徑規(guī)劃的熱門應(yīng)用有高德地圖、百度地圖等App，但它們也只提供了支持公交、駕車及步行三種出行方式的點(diǎn)到點(diǎn)的路徑規(guī)劃，對(duì)于從起點(diǎn)經(jīng)過(guò)多個(gè)沿途點(diǎn)到達(dá)終點(diǎn)的路線規(guī)劃并未涉及。鑒于目前尚未有將路徑規(guī)劃與iOS移動(dòng)平臺(tái)的應(yīng)用特點(diǎn)充分相結(jié)合的應(yīng)用，本文就設(shè)計(jì)開(kāi)發(fā)了iOS平臺(tái)上基于電子地圖的路徑規(guī)劃系統(tǒng)——稱之為“易配送系統(tǒng)”。易配送系統(tǒng)可在用戶使用期間自動(dòng)定位用戶當(dāng)前所在位置，同時(shí)提供倉(cāng)庫(kù)到各配送點(diǎn)的路線規(guī)劃和導(dǎo)航等主要功能，還通過(guò)服務(wù)端的接口服務(wù)將數(shù)據(jù)封裝成XML編碼格式通過(guò)網(wǎng)絡(luò)提供給客戶端，保障了訂單數(shù)據(jù)的真實(shí)性與實(shí)時(shí)性。在系統(tǒng)開(kāi)發(fā)過(guò)程中利用高德iOS地圖SDK進(jìn)行應(yīng)用開(kāi)發(fā)，提供了可視化的路徑規(guī)劃人機(jī)交互界面。

本文的內(nèi)容首先對(duì)iOS平臺(tái)開(kāi)發(fā)相關(guān)技術(shù)進(jìn)行了簡(jiǎn)要介紹，然后對(duì)訂單配送路徑規(guī)劃系統(tǒng)進(jìn)行分析，設(shè)計(jì)出了整體的技術(shù)方案與系統(tǒng)架構(gòu)，然后對(duì)系統(tǒng)功能進(jìn)行詳細(xì)實(shí)現(xiàn)，包括倉(cāng)庫(kù)、訂單查詢，地圖位置顯示、路線規(guī)劃及導(dǎo)航等功能，最后進(jìn)行結(jié)果分析與總結(jié)。

1 iOS開(kāi)發(fā)平臺(tái)介紹

1.1 iOS系統(tǒng)架構(gòu)

iOS平臺(tái)應(yīng)用的開(kāi)發(fā)語(yǔ)言主要有Objective-C和Swift語(yǔ)言，由于swift作為一門新生語(yǔ)言使用人數(shù)較少的原因，本系統(tǒng)采用了主流開(kāi)發(fā)語(yǔ)言O(shè)bjective-C進(jìn)行編碼開(kāi)發(fā)。Objective-C作為ANSI C的超集[4]，不僅擴(kuò)展了面向?qū)ο笤O(shè)計(jì)的能力，如類、消息、繼承，同時(shí)它可以調(diào)用C的函數(shù)，也可以通過(guò)C++對(duì)象訪問(wèn)方法，具有對(duì)C和C++語(yǔ)言的兼容性。

蘋果公司最新推出的iOS 10 SDK （Software Development Kit， 軟件開(kāi)發(fā)工具包）增加了新的API （Application Programming Interface， 應(yīng)用程序編程接口）和服務(wù)，能夠支持更多新類型的應(yīng)用程序和功能。目前基于iOS平臺(tái)開(kāi)發(fā)的應(yīng)用程序可以擴(kuò)展到消息、Siri、電話和地圖等系統(tǒng)自帶服務(wù)，擁有了更吸引人的功能。圖1為iOS系統(tǒng)架構(gòu)圖：

圖中可觸摸層主要提供用戶交互相關(guān)的服務(wù)如界面控件、事件管理、通知中心、地圖，包含以下框架：UIKit、Notification Center、MapKit等；媒體層主要提供圖像引擎、音頻引擎及視頻引擎框架；核心服務(wù)層為程序提供基礎(chǔ)的系統(tǒng)服務(wù)如網(wǎng)絡(luò)訪問(wèn)、瀏覽器引擎、定位、文件訪問(wèn)、數(shù)據(jù)庫(kù)訪問(wèn)等。最底層的核心系統(tǒng)層為上層結(jié)構(gòu)提供了最基礎(chǔ)的服務(wù)包括操作系統(tǒng)內(nèi)核服務(wù)、本地認(rèn)證、安全、加速等。

1.2 iOS 地圖SDK

iOS 地圖SDK 是高德提供的一套基于 iOS 6.0.0 及以上版本的地圖應(yīng)用程序開(kāi)發(fā)接口，供開(kāi)發(fā)者在iOS應(yīng)用中加入地圖相關(guān)的功能[6]。它提供的四種地圖模式包括：標(biāo)準(zhǔn)地圖、衛(wèi)星地圖、夜景模式地圖和導(dǎo)航模式地圖。開(kāi)發(fā)者不僅可以利用其地圖計(jì)算工具實(shí)現(xiàn)坐標(biāo)轉(zhuǎn)換和距離或面積計(jì)算，而且可以調(diào)用API完成出行路線規(guī)劃及點(diǎn)標(biāo)注、折線、面的繪制等工作。這些實(shí)現(xiàn)的提前需要注冊(cè)并認(rèn)證成為高德開(kāi)發(fā)者，接著為應(yīng)用申請(qǐng)APIKey，然后將iOS地圖SDK配置到應(yīng)用工程中，這里可以采用手動(dòng)和自動(dòng)化兩種配置方式。前者的配置過(guò)程簡(jiǎn)單易操作，但更新操作代價(jià)大，后者配置過(guò)程稍顯負(fù)雜，但更新很方便。手動(dòng)配置的方式則需要手動(dòng)向工程項(xiàng)目中導(dǎo)入MAMapKit.framework和AMapSearchKit. framework兩個(gè)包，當(dāng)框架有更新時(shí)需將工程中舊框架刪除并添加新框架，其使用稍顯麻煩。本系統(tǒng)的實(shí)現(xiàn)采用了自動(dòng)化配置工程的方式，利用第三方庫(kù)管理工具CocoaPods通過(guò)命令：pod ‘AMap3DMap， ‘～>4.0和pod ‘AMapSearch， ‘～>4.0完成自動(dòng)導(dǎo)入框架的目的，當(dāng)框架更新時(shí)只需執(zhí)行pod update即可實(shí)現(xiàn)項(xiàng)目中框架的更新。

2 整體方案設(shè)計(jì)

通常App功能復(fù)雜的情況下需要有后臺(tái)服務(wù)器的業(yè)務(wù)處理支持，本文涉及的路徑規(guī)劃功能需要處理的計(jì)算量會(huì)隨著配送點(diǎn)個(gè)數(shù)的增長(zhǎng)呈指數(shù)階上升，因此需要后臺(tái)服務(wù)器的強(qiáng)大計(jì)算能力處理路徑規(guī)劃結(jié)果，進(jìn)而減輕客戶端內(nèi)存使用壓力。

本系統(tǒng)整體技術(shù)方案的設(shè)計(jì)綜合考慮了移動(dòng)應(yīng)用端、服務(wù)端（包括應(yīng)用服務(wù)器和提供商服務(wù)器）以及數(shù)據(jù)庫(kù)服務(wù)器三部分所涉及的技術(shù)及其簡(jiǎn)要的功能模塊劃分，如下圖2所示：

其中應(yīng)用服務(wù)端是典型的電商進(jìn)銷存管理系統(tǒng)，移動(dòng)端LBS應(yīng)用——易配送App的實(shí)現(xiàn)需要在進(jìn)銷存Web系統(tǒng)的表示層、業(yè)務(wù)邏輯層、數(shù)據(jù)持久層添加相應(yīng)的訂單配送接口，該接口將服務(wù)端經(jīng)過(guò)處理的數(shù)據(jù)結(jié)果封裝成XML標(biāo)準(zhǔn)的數(shù)據(jù)格式通過(guò)HTTP協(xié)議傳輸給App。

3 基于iOS的路徑規(guī)劃App設(shè)計(jì)

3.1 App開(kāi)發(fā)模式

易配送App采用Objective-C開(kāi)發(fā)語(yǔ)言，開(kāi)發(fā)工具為Xcode7.0，主要針對(duì)iPhone進(jìn)行設(shè)計(jì)的。系統(tǒng)的設(shè)計(jì)模式采用了MVC范型如圖3。由于系統(tǒng)所涉及的內(nèi)容數(shù)據(jù)均通過(guò)網(wǎng)絡(luò)請(qǐng)求服務(wù)器實(shí)時(shí)更新獲取，故采用了iOS App開(kāi)發(fā)模式中的Native App，以保證有較好的網(wǎng)絡(luò)環(huán)境以及節(jié)省的帶寬，以便利用充分的設(shè)備資源來(lái)提供良好的交互體驗(yàn)。

該系統(tǒng)平臺(tái)中的位置信息主要體現(xiàn)在：位置服務(wù)和地圖。位置服務(wù)是由Core Location框架負(fù)責(zé)，它將用戶的位置及方向信息以O(shè)bjective-C語(yǔ)言能識(shí)別的形式羅列出來(lái)[4]；地圖服務(wù)通過(guò)應(yīng)用中集成的高德開(kāi)發(fā)平臺(tái)提供的MAMapKit框架負(fù)責(zé)，利用它可以展示出地圖和圖釘標(biāo)注等信息。易配送App的路徑規(guī)劃模塊有效地將Core Location框架和MAMapKit框架結(jié)合起來(lái)，以實(shí)現(xiàn)地圖定位、距離測(cè)試、路線顯示及導(dǎo)航功能。

3.2 重要功能設(shè)計(jì)及關(guān)鍵技術(shù)實(shí)現(xiàn)

系統(tǒng)的主界面設(shè)計(jì)采用了圖文結(jié)合的布局方式如圖4，使用戶能夠快速便捷的操作系統(tǒng)。對(duì)于信息查詢類似功能的界面多采用表視圖結(jié)構(gòu)，得到了清楚地展示大量?jī)?nèi)容信息的效果如圖5所展示的待配送訂單列表。

圖4 主界面 圖5 待配送列表

圖6 路徑規(guī)劃

系統(tǒng)主要的路徑規(guī)劃功能在電子地圖的地理信息背景下完成了標(biāo)注及路線可視化如圖6所示，其關(guān)鍵技術(shù)的實(shí)現(xiàn)如下：

1）初始化地圖服務(wù)

系統(tǒng)中地圖服務(wù)的使用首先需要初始化地圖控件，這需要在創(chuàng)建MAMapView之前需要先綁定APIKey：[MAMapServices sharedServices].apiKey = APIKey； 和[AMapSearchServices sharedServices].apiKey = APIKey；接著初始化MAMapView地圖控件：_mapView = [[MAMapView alloc] initWithFrame： self.view. frame]；并給系統(tǒng)添加地圖視圖：[self.view addSubview：_mapView]；

2）分組待配送訂單

因?yàn)闃I(yè)務(wù)要求需要將待配送訂單按各自對(duì)應(yīng)的出貨倉(cāng)庫(kù)進(jìn)行分組配送，系統(tǒng)中通過(guò)自定義實(shí)現(xiàn)分組方法：-（void）groupAction：（NSMutableArray *）array； 其中參數(shù)array中存儲(chǔ)著多個(gè)配送單對(duì)象XJDeliveryOrder。方法實(shí)現(xiàn)中利用可變的集合對(duì)象NSMutableSet保存的內(nèi)容對(duì)象不重復(fù)的特性，用_warehouseSet記錄不同的倉(cāng)庫(kù)信息：_warehouseSet = [NSMutableSet set]； [array enumerateObjectsUsing Block： ^（ XJDeliveryOrder * _Nonnull order， NSUInteger idx， BOOL * _Nonnull stop） {[_warehouseSet addObject：order.warehouseName]； }]； 同時(shí)該方法中利用謂詞NSPredicate過(guò)濾數(shù)組array實(shí)現(xiàn)按倉(cāng)庫(kù)名稱分組：[_warehouseSet enumerateObjectsUsingBlock：^（NSString * _Nonnull warehouseName， BOOL * _Nonnull stop） {NSPredicate *predicate = [NSPredicate predicateWithFormat： @"warehouseName = %@"， warehouseName]；NSArray *tempArr = [NSArray arrayWithArray：[array filteredArrayUsingPredicate：predicate]]； [groupArr addObject： tempArr]；}]；

3）添加標(biāo)注及氣泡視圖

給地圖添加標(biāo)注需要調(diào)用地理編碼請(qǐng)求：[self.search AMapGeocodeSearch： geo]； 其中對(duì)象geo為AMapGeocodeSearchRequest類對(duì)象且其屬性值address不為空，該請(qǐng)求會(huì)回調(diào)AMapSearchDelegate中的方法：- （void）onGeocodeSearchDone： （AMapGeocodeSearchRequest*）request response：（AMapGeocodeSearchResponse *） response；其中response對(duì)象中包含了經(jīng)緯度信息并且該方法中調(diào)用了添加標(biāo)注方法：[_mapView addAnnotation：pointAn]；其中對(duì)象pointAn為MAPointAnnotation類對(duì)象。

實(shí)現(xiàn)觸摸標(biāo)注彈出氣泡的效果需要實(shí)現(xiàn)MAMapViewDelegate委托中-（MAAnnotationView*）mapView：（MAMapView*）mapViewviewForAnnotaion： （id< MAAnotation>）annotation；和-（void）mapView：（MAMapView*）mapView didSelect AnnotationView：（MAAnnotationView *）view；方法。

4）路徑規(guī)劃及繪制路線

iOS地圖API提供了按參數(shù)順序進(jìn)行路徑規(guī)劃的方法：[_search AMapDriving RouteSearch：request]；其中request為AMapDrivingRouteSearchRequ -est對(duì)象，需要給定request的屬性：起點(diǎn)origin、終點(diǎn)destination和沿途點(diǎn)waypoints的值。而對(duì)于最優(yōu)路徑的規(guī)劃只能通過(guò)自定義方法：-（void）planBestPaths WithLoaction：（CLLocationCoordinate2D）location wayPoints： （NSArray*） wayPoints；該方法中調(diào)用了網(wǎng)絡(luò)請(qǐng)求服務(wù)器方法，并能夠獲取服務(wù)器返回的處理結(jié)果，其結(jié)果中包含了多個(gè)經(jīng)緯度字符串，需要利用方法- （CLLocationCoordinate2D *）coordinatesForString：（NSString*）string coordinateCount：（NSUInteger *）coordinate Count parseToken：（NSString *）token；來(lái)解析經(jīng)緯度，然后系統(tǒng)利用解析得到的經(jīng)緯度調(diào)用[MAPolyline polylineWithCoordinates：coordinates count：count]來(lái)繪制路線。

5）最優(yōu)路徑算法

本系統(tǒng)的服務(wù)端路徑規(guī)劃接口實(shí)現(xiàn)中采用了適合解決單回路最短路徑問(wèn)題的算法——最近點(diǎn)插入算法。最近插入法是一種啟發(fā)式算法，它不僅適用于各種復(fù)雜的TSP問(wèn)題，對(duì)于中小規(guī)模問(wèn)題同樣適用。圖7為算法具體流程。算法的實(shí)現(xiàn)是在后臺(tái)服務(wù)端通過(guò)java語(yǔ)言實(shí)現(xiàn)的，這里就不做詳細(xì)說(shuō)明了。

4 系統(tǒng)測(cè)評(píng)與應(yīng)用實(shí)例

為了對(duì)系統(tǒng)的功能及路徑優(yōu)化效果進(jìn)行測(cè)試，采用了如下的實(shí)驗(yàn)環(huán)境：客戶端是所有系統(tǒng)為iOS 7.0及以上iPhone手機(jī)，安裝App后即可使用；服務(wù)端為可安裝運(yùn)行在windows平臺(tái)下的進(jìn)銷存管理系統(tǒng)；數(shù)據(jù)庫(kù)為Oracle數(shù)據(jù)庫(kù)安裝在Linux數(shù)據(jù)庫(kù)服務(wù)器上。

本系統(tǒng)中路徑規(guī)劃功能的實(shí)現(xiàn)采用了將多個(gè)倉(cāng)庫(kù)多配送點(diǎn)的路徑規(guī)劃分解為多個(gè)單倉(cāng)庫(kù)多點(diǎn)配送的思想。下面一系列圖示說(shuō)明了多個(gè)單倉(cāng)庫(kù)出發(fā)到多個(gè)配送點(diǎn)的路徑規(guī)劃對(duì)比結(jié)果。

圖8中顯示當(dāng)天需要規(guī)劃路徑的所有點(diǎn)，包括三個(gè)倉(cāng)庫(kù)和八個(gè)客戶位置。接下來(lái)分別對(duì)三個(gè)倉(cāng)庫(kù)進(jìn)行出貨配送安排，如圖9為從總倉(cāng)庫(kù)出發(fā)的配送路線對(duì)比，其中上圖為按下單順序依次配送的路線圖，下圖為根據(jù)與出發(fā)倉(cāng)庫(kù)距離由近到遠(yuǎn)的依次配送的路線圖，從圖中可以明顯看出兩者各自的路程代價(jià)，表1為各倉(cāng)庫(kù)配送路徑的對(duì)比結(jié)果。

通過(guò)實(shí)驗(yàn)測(cè)試結(jié)果表明，當(dāng)單次規(guī)劃的配送數(shù)量小于等于6時(shí)，本系統(tǒng)的最優(yōu)路徑準(zhǔn)確且計(jì)算處理很快，幾乎網(wǎng)絡(luò)無(wú)延遲。當(dāng)單次規(guī)劃的配送數(shù)量大于6小于17時(shí)，優(yōu)化結(jié)果準(zhǔn)確但是處理速度變慢，并且處理響應(yīng)時(shí)間雖配送數(shù)量呈現(xiàn)指數(shù)階增長(zhǎng)。當(dāng)單次規(guī)劃的配送數(shù)量大于16時(shí)，服務(wù)端需通過(guò)一定路徑優(yōu)化算法處理大規(guī)模計(jì)算，但其結(jié)果往往是最優(yōu)解的近似值而非最優(yōu)路徑值。

5 結(jié)束語(yǔ)

本文是在iOS系統(tǒng)上基于電子地圖的應(yīng)用開(kāi)發(fā)，基本實(shí)現(xiàn)了小規(guī)模訂單配送的路徑規(guī)劃功能。經(jīng)過(guò)優(yōu)化的路徑的確節(jié)省了許多里程，真正意義上為企業(yè)提高了效益。但是本系統(tǒng)還存在一些不足之處，如適合處理小規(guī)模訂單配送路徑規(guī)劃的局限性，系統(tǒng)的可擴(kuò)展性有待加強(qiáng)。在今后的學(xué)習(xí)和研究中，將進(jìn)一步深化和擴(kuò)展該應(yīng)用的功能，提供更加豐富的視圖信息和交互方式，實(shí)現(xiàn)更良好的路徑規(guī)劃體驗(yàn)。

參考文獻(xiàn)：

[1] WANG Tiejun，WU Kaijun. Study multi-depots vehicle routing based on improve -ed particle swarm optimization[J]. Computer Engineering and Applications，2013， 49（2）： 5-8.

[2] 馬建華，房勇，袁杰.多車場(chǎng)多車型最快完成車輛路徑問(wèn)題的變異蟻群算法[J].系統(tǒng)工程理論與實(shí)踐，2011（8）.

[3] 李波，邱紅艷.基于雙層模糊聚類的多車場(chǎng)車輛路徑遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2014（5）.

[4] 胡楊帆，楊剛，胡顥石.結(jié)合LBS和信息推送的博物館App的設(shè)計(jì)實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件，2013， 12（30）：108-112.

[5] 百度百科.手機(jī)定位技術(shù)[EB/OL].http：//baike.baidu.com/link？url=FdVsR1eUHO4pXu -1mDnBoar4VvjzDHE03VEw3qj0ZrX NvdqZ4NjURdzUm75kq8pxLjsAThN-8FjBpzdAWdeYnBVKIcwngDEQ6NwR8K9F-Pemfn634NrVYuoNjNbF_leE_sq_lqJotl 5_ZxKi4Eiy5K.

[6] 高德開(kāi)發(fā)平臺(tái).高德地圖iOS SDK簡(jiǎn)介[EB/OL]. http：//lbs.amap.com/api/ios-sdk/summa ry/.