純手工打造每一篇開源資訊與技術(shù)干貨，數(shù)十萬程序員和Linuxer已經(jīng)關(guān)注。

物流行業(yè)是被電子商務(wù)催生的產(chǎn)業(yè)之一。

快件的配送和攬件的調(diào)度算法是物流行業(yè)一個非常重要的課題，直接關(guān)系到配送或攬件的時效，以及物流公司的運(yùn)作成本。

好的算法，可以提高時效，降低成本，甚至可以更好的調(diào)動社會資源。

本文將以物流行業(yè)為例，給大家分析一下 PostgreSQL 與 Greenplum 在地理位置信息處理，最佳路徑算法，機(jī)器學(xué)習(xí)等方面的物流行業(yè)應(yīng)用方法。

物流做的事情很簡單，寄件，送件（但是后面蘊(yùn)藏著很多高精尖的黑科技呢，比如怎么調(diào)度，怎么獲得最佳路徑）。

物流環(huán)節(jié)的要素有幾個，都與位置有關(guān)。

• 寄件人

• 攬件員（攬件人通常不是直接將貨收到倉庫，而是網(wǎng)點。所以網(wǎng)點到倉庫也是需要調(diào)度的，本文未涉及。）

• 調(diào)度方法與配送差不太多。

• 貨物

• 倉庫

• 運(yùn)輸工具

• 派件員

• 收件人

我們這里先從簡單的入手，假設(shè)現(xiàn)在只關(guān)心位置信息，剖析一下從寄件到收到包裹，整個過程串起來，看看背后的技術(shù)。

1. 寄件

貨物從寄件人到攬件員，通常是預(yù)約的操作，而且寄件人可以直接去網(wǎng)點辦理寄件，所以沒有太多的算法在里面。

如果派件和攬件混合在一起的話，可以用 KNN 算法來解決，再結(jié)合派件點路徑調(diào)度，選出最佳的攬件人。

例如，寄件人當(dāng)前位置，與快遞員調(diào)度的下一個位置，進(jìn)行 KNN 運(yùn)算，因此 B 來攬件是成本最低的。

2. 貨物在倉庫之間流轉(zhuǎn)的物流調(diào)度

假設(shè)上圖為倉庫的位置，兩個倉庫之間如果開通了線路的話，就以線段連接起來。

每個倉庫負(fù)責(zé)一個區(qū)域，這個區(qū)域是一個幾何的圖形。

通過寄件人和收件人的位置，與倉庫的區(qū)域進(jìn)行點面判斷，找出寄件人的倉庫與收件人的倉庫。

快件為點，倉庫為面，寄件時根據(jù)寄件人填寫的寄件和收件信息轉(zhuǎn)換為寄件和收件兩個經(jīng)緯度，通過這兩個經(jīng)緯度與快遞公司的倉庫表進(jìn)行點面包含的判斷匹配，就可以找出快件對應(yīng)的起點和終點的倉庫。

點面判斷。

有了源和目標(biāo)就可以通過 pgrouting 提供的各種最佳路徑算法算出每件貨物的最佳路徑。

本文后面會有 demo 來講解如何使用 pgrouting 計算最佳路徑。

倉庫之間的貨車的工作就簡單了，裝滿就走或分波次(考慮到時效) 的原則，負(fù)責(zé)好兩個直連節(jié)點的來回運(yùn)輸，并不是一輛車完成整個貨物的從起點到終點的運(yùn)輸。

例如負(fù)責(zé) A 和 B 之間線路的貨車，只在 AB 之間跑運(yùn)輸。

3. 貨物從終點倉庫到網(wǎng)點的物流調(diào)度

貨物在抵達(dá)目標(biāo)倉庫后，首先要將貨物分揀到派件的網(wǎng)點。

其實也是一個點面判斷的過程，網(wǎng)點覆蓋的派件范圍為面，快件則為點，點面判斷找出對應(yīng)的網(wǎng)點。

從倉庫到網(wǎng)點，也可以使用倉庫建流轉(zhuǎn)的原理，計算出最佳線路。貨車只負(fù)責(zé)2個網(wǎng)點之間的貨物流轉(zhuǎn)即可。

4. 派件

進(jìn)入派件的流程，也就是貨物在抵達(dá)收件人手中的最后一公里要做的事情。

為了更好的實現(xiàn)派件調(diào)度，需要對快件進(jìn)行聚合操作，根據(jù)位置進(jìn)行聚合。

原理和前面類似，還是要做點面判斷，只是目標(biāo)更加精確，例如精確到小區(qū)或者很小的區(qū)域。

派件除了要考慮快件的目的地（聚合后的），還需要考慮快件的體積，重量，以及快遞員的運(yùn)貨能力（體積與重量） 。

假設(shè)一個網(wǎng)點當(dāng)前收到的快件覆蓋了以下需要派送的點（聚合后的），同時每個點的貨物體積總和如數(shù)字所表示。

路徑規(guī)劃與前面不一樣的地方，這里規(guī)劃的是多個點作為目標(biāo)。

多點目標(biāo)的最佳路徑，用意是確保相鄰目標(biāo)的連續(xù)性，確保切分不同網(wǎng)點的快件后，拿到快件的人跑的依舊是相鄰的點。

例如中心是網(wǎng)點的位置，其他點是目標(biāo)位置，目標(biāo)位置的數(shù)字是體積，假設(shè)每個快遞員一次運(yùn)輸?shù)捏w積是 7000，虛線是一個快遞員拿到的一趟的快件。

這種方法確保了每趟的快件是連續(xù)的。

多點目標(biāo)的最佳路徑規(guī)劃，在本文后面的部分也會有 DEMO。

如何將地址轉(zhuǎn)換成坐標(biāo)，不在本文的討論范圍，很多做導(dǎo)航的公司都可以輸出這個能力。

但是作為快遞公司，還有一種方法可以獲得精確的坐標(biāo)信息，例如快遞員的手持GPS終端，收件時掃個條碼，同時上報位置信息。

有了一定的基數(shù)后，通過文本分析和機(jī)器學(xué)習(xí)，也可以輸出地址轉(zhuǎn)坐標(biāo)的能力。

如果基數(shù)非常龐大，可以選擇基于 PostgreSQL 的 Greenplum 數(shù)據(jù)倉庫，進(jìn)行文本分析與機(jī)器學(xué)習(xí)(支持 MADlib 庫，支持R，python，java)。

PS：

Greenplum 支持文本分析，支持地理位置信息處理，支持 MADlib 機(jī)器學(xué)習(xí)庫，還支持 R 語言自定義函數(shù)，python 函數(shù)，支持分布式并行計算。

最重要的是它開源，絕對是有文本和地理位置分析需求的用戶最好的選擇。

你可以使用熟悉的 R、Python、Java 自定義數(shù)據(jù)庫端的 UDF，滿足靈活的業(yè)務(wù)需求。

以倉庫之間的數(shù)據(jù)流轉(zhuǎn)為例：

需要用到 PostgreSQL 數(shù)據(jù)庫的 PostGIS 與 pgrouting。

首先是基礎(chǔ)數(shù)據(jù)的錄入，即道路數(shù)據(jù)，用來表示開通了運(yùn)輸航線的倉庫之間的線段數(shù)據(jù)，以及線段的屬性信息。

1. 生成拓?fù)?/strong>

有了道路信息還不夠，要生成最佳路徑，首先要生成合法的拓?fù)洌駝t怎么生成路徑呢？

生成拓?fù)淝埃枰砑觾蓚€字段，用來存儲線段的首尾編號。

調(diào)用 pgr_createTopology 生成拓?fù)?，也就是生成線段的首位編號的過程

例如，ABC 三條線段，其中 B 線段的兩端都沒有和 AC 完全吻合，誤差分別為 1 米和 10 米，所以需要設(shè)置容錯。

生成線段，實際上就是設(shè)置 source 和 target 的 ID，設(shè)置完后，可能就變成這樣的了。

2. 生成最佳路徑

我們知道道路是有坡度，有彎度的，還有顛簸程度，是否單行線，過路費(fèi)，擁堵程度，怎么送貨效率最高，不能只看路程。

想象一下你打車去機(jī)場的場景，如果時間比較緊的話，就要靠司機(jī)了。

一個優(yōu)秀的出租車司機(jī)是會幫你選擇最佳路徑的，算上擁堵費(fèi)，繞路其實可能更省。

pgrouting 支持的最佳路徑算法很多

你可以根據(jù)不同的算法，輸入當(dāng)時每條路段相關(guān)的因素（例如坡度，彎度，顛簸程度，是否單行線，過路費(fèi)，擁堵程度 數(shù)字化的 weight 系數(shù)），生成最佳路徑。

支持的內(nèi)置算法如圖