?

某天中午，?編喜滋滋地點了?份??飯外賣，然后翹?以盼等待配送?哥的到來。半個多?時過去了，軟件上的地圖顯??哥離我只有三百?的距離，??飯已經近在咫尺。然?左等右等??飯也沒有到，再打開app?看，簡直兩眼發?：?哥的距離竟然從三百?變成了 ?千?！

相信?家都曾遇到過這樣的問題：外賣點的各種美?，或者跑腿購買的東西，還有淘寶的包裹，明明頁?顯?它們已經近在咫尺甚?只有?分鐘的路程，結果配送?哥?要繞遠去別的地?，

在家翹?以盼包裹到來的你等到花?都快謝了，讓你?語凝咽： 軟件上的路線規劃完全是??智障！ 然?，好奇?旺盛的?編陷?了沉思，為何這路線規劃顯得如此智障呢，莫?這??隱藏著某些不 為?知的秘密？這究竟是?性的缺失還是算法的淪喪？

剛好，天池最后?公?配送問題?賽提供了配送機制以及這個問題需要的數據，讓我們來?探究竟。

?

?

-配送機制-

?

我們來看看淘寶的配送機制：

·配送?員從?點將包裹配送到客戶?上?

·每個配送員最多只能攜帶140個包裹?

·送完所有的包裹回到?點?

·配送點與?點的從屬關系固定

?

-數據介紹-

?

?樣?，使?pandas讀取并觀察數據：

            
              import?pandas?as?pd
tp1=pd.read_csv(r"F:\data\tianchi\peisong\peisongshuju\1.csv",sep=",")
tp2=pd.read_csv(r"F:\data\tianchi\peisong\peisongshuju\2.csv",sep=",")
tp3=pd.read_csv(r"F:\data\tianchi\peisong\peisongshuju\4.csv",sep=",")
tp1.head()# 點ID以及對應的經度和緯度
            
          

            
              tp2.head()#配送點ID以及對應的經度和緯度
            
          

            
              tp3.head()#訂單ID，配送點ID，點ID以及需要送配送點的電商包裹量
            
          

            我們來看單個?點的路線規劃，先將A117?點數據整合在?張表?：

          

            
              #整合A117點的整合A117點數據
tp1=tp1.set_index('Site_id')
a="A117"
a1=tp3[tp3.Site_id=="A117"]
a1=pd.merge(a1,tp2) #獲取對應配送點的坐標
a1.Lng=a1.Lng-tp1.loc["A117"]["Lng"]
a1.Lat=a1.Lat-tp1.loc["A117"]["Lat"]
#以網點為原點，只看配送點與點之間的相對坐標
a1.head()
            
          

            觀察配送點與?點的位置關系:

          

            
              import?pylab
pylab.plot([0],[0],"o")
pylab.plot(a1.Lat.values,a1.Lng.values,"o")
            
          

            如圖所?，藍?的點是?點A117的位置，黃?的點是配送點的位置，配送?哥從藍?點出發，把包裹送到黃?點，每次攜帶的包裹不?于140個。當攜帶的包裹配送完后，配送?哥需要再次返回到 ?點取包裹。路線規劃所考慮的問題是：怎么?才能使配送?哥?的路程最短呢？為了簡化起見，我們將經緯度下的曲線距離?直線距離來代替。

          

?

路線規劃?：基于點的?度順序配送

物流配送路徑優化問題是?個很經典的問題，針對該問題有很多的解決?法。基于點的?度順序配 送是?個?較簡單且運?良好的算法。

            如上圖所?，P0為起始點，其它點為配送需求點。

          

1. 采?極坐標來表?各點的相對位置，然后以P0點為坐標原點，以P1為起始點，定其?度為零 度，以順時鐘或逆時鐘?向開始掃描各個點，獲得各點與原點連線P0Pn相對于P0P1的?度? ?。

2. 根據?度??確定其順序，直?掃描完畢。?

3. 掃描結束后獲得的點的序列就是各點的配送順序。?

了解了算法原理，我們來試驗?下，A117這個?點的配送順序是如何的。

?

下?，就開始路線規劃啦：

            
              a1=pd.concat([a1,a1.Lng/a1.Lat],axis=1) #計算各個配送點的正切值 a1.rename(columns={0:"zhengqie"},inplace=True)
a1=pd.concat([a1,(a1.Lng**2+a1.Lat**2)**0.5],axis=1)#計算各個配送點與中點的距離
a1.rename(columns={0:"r"},inplace=True)
lu1=a1[a1.Lat>0].sort_values(["zhengqie"])
lu2=a1[a1.Lat<0].sort_values(["zhengqie"])
lu=pd.concat([lu1,lu2])

zz=0
x=[0]
y=[0]
ju=0
lat=0
lng=0

for?i?in?lu.iterrows():
zz=zz+i[1]["Num"]
if?zz>140:
x.append(0)
y.append(0)
pylab.plot(x,y,"-o")
ju=ju+(lat**2+lng**2)**0.5 #加回程距離
lat=0
lng=0
x=[0]
y=[0]
zz=i[1]["Num"]
ju=ju+((i[1]["Lat"]-lat)**2+(i[1]["Lng"]-lng)**2)**0.5#加 了路徑長度的計算

lat=i[1]["Lat"]
lng=i[1]["Lng"]

x.append(lat)
y.append(lng)
ju=ju+((0-lat)**2+(0-lng)**2)**0.5
x.append(0)
y.append(0)
print(ju)
pylab.plot(x,y,"-o")
pylab.show()
            
          

            通過這份路線規劃圖，就不難明?配送?哥為何會繞遠了。以順時針?向進?配送 假設你在圖中1的位置， 配送?哥正在2的位置進?配送， 按照實際距離來講，快遞?哥離你最近，下?個應該?先為你進?配送，但是根據?度??來規劃路線，快遞?哥卻去了更遠的3這個位置！
          

            我餓著肚子癡癡地等待著我的牛肉飯，明明我是最近的，卻讓我白白地多等了半個小時，就因為我家地理位置的正切值比別人家的大？這路線規劃一點兒也不合理！別急，我們來看看另一種路線規劃方法。
          

?

路線規劃?：環形掃描法

由于僅僅按照?度順序分配，導致徑向距離來回的浪費。因此我們把點分為不同徑向長度的環，環內按照?度排序，減少徑向??。

            
              def c1(a):#點與配送點的數據準
a1=tp3[tp3.Site_id==a]
a1=pd.merge(a1,tp2)
a1.Lng=a1.Lng-tp1.loc[a]["Lng"]
a1.Lat=a1.Lat-tp1.loc[a]["Lat"]
a1=pd.concat([a1,a1.Lng/a1.Lat],axis=1)
a1.rename(columns={0:"zhengqie"},inplace=True)
a1=pd.concat([a1,(a1.Lng**2+a1.Lat**2)**0.5],axis=1)
a1.rename(columns={0:"r"},inplace=True)
return a1

def c2(a1):#?度排序
lu1=a1[a1.Lat>0].sort_values(["zhengqie"])
lu2=a1[a1.Lat<0].sort_values(["zhengqie"])
return pd.concat([lu1,lu2])

def c3(lu):#按照最140的負荷布置路徑
zz=0
x=[0]
y=[0]
ju=0
lat=0
lng=0

for i in lu.iterrows():
zz=zz+i[1]["Num"]
if zz>140:
x.append(0)
y.append(0)
pylab.plot(x,y,"-o")
ju=ju+(lat**2+lng**2)**0.5
lat=0
lng=0
x=[0]
y=[0]
zz=i[1]["Num"]
ju=ju+((i[1]["Lat"]-lat)**2+(i[1]["Lng"]-lng)**2)**0.5
lat=i[1]["Lat"]
lng=i[1]["Lng"]
x.append(lat)
y.append(lng)
ju=ju+((0-lat)**2+(0-lng)**2)**0.5
x.append(0)
y.append(0)
pylab.plot(x,y,"-o")
pylab.show()
return ju

p1=c1(a) #數據處理
r0=p1.r.mean()#配送點與 點的平均距離
h0=p1[p1.r
              
            
          

            使用環形掃描法 基本的掃描法效果好了很多。配送哥少跑了很多冤枉路，但是可以看到，它仍然法完全解決你的困擾！
          

            若為順時針掃描，假設你在位置1，配送?哥正在位置2，雖然你距離他很近，但仍然，他需要先到 達更遠的位置3，再到你的位置！

事實上，通過其他算法也可以得到或近似得到配送?哥的最短路徑規劃?案。但不論如何，配送?哥距離你的位置最近就?定會為你最先配送嗎？

答案是否定的！畢竟考慮到配送?哥?作量如此之?，在家嗷嗷待哺的我們就稍微耐??點吧！

          

想要獲取更多數據科學知識干貨，歡迎關注我們的公眾號【DC黑板報】

?

?

?