?

某天中午，?編喜滋滋地點(diǎn)了?份??飯外賣(mài)，然后翹?以盼等待配送?哥的到來(lái)。半個(gè)多?時(shí)過(guò)去了，軟件上的地圖顯??哥離我只有三百?的距離，??飯已經(jīng)近在咫尺。然?左等右等??飯也沒(méi)有到，再打開(kāi)app?看，簡(jiǎn)直兩眼發(fā)?：?哥的距離竟然從三百?變成了 ?千?！

相信?家都曾遇到過(guò)這樣的問(wèn)題：外賣(mài)點(diǎn)的各種美?，或者跑腿購(gòu)買(mǎi)的東西，還有淘寶的包裹，明明頁(yè)?顯?它們已經(jīng)近在咫尺甚?只有?分鐘的路程，結(jié)果配送?哥?要繞遠(yuǎn)去別的地?，

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

剛好，天池最后?公?配送問(wèn)題?賽提供了配送機(jī)制以及這個(gè)問(wèn)題需要的數(shù)據(jù)，讓我們來(lái)?探究竟。

?

?

-配送機(jī)制-

?

我們來(lái)看看淘寶的配送機(jī)制：

·配送?員從?點(diǎn)將包裹配送到客戶?上?

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

·送完所有的包裹回到?點(diǎn)?

·配送點(diǎn)與?點(diǎn)的從屬關(guān)系固定

?

-數(shù)據(jù)介紹-

?

?樣?，使?pandas讀取并觀察數(shù)據(jù)：

            
              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()# 點(diǎn)ID以及對(duì)應(yīng)的經(jīng)度和緯度
            
          

            
              tp2.head()#配送點(diǎn)ID以及對(duì)應(yīng)的經(jīng)度和緯度
            
          

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

            我們來(lái)看單個(gè)?點(diǎn)的路線規(guī)劃，先將A117?點(diǎn)數(shù)據(jù)整合在?張表?：

          

            
              #整合A117點(diǎn)的整合A117點(diǎn)數(shù)據(jù)
tp1=tp1.set_index('Site_id')
a="A117"
a1=tp3[tp3.Site_id=="A117"]
a1=pd.merge(a1,tp2) #獲取對(duì)應(yīng)配送點(diǎn)的坐標(biāo)
a1.Lng=a1.Lng-tp1.loc["A117"]["Lng"]
a1.Lat=a1.Lat-tp1.loc["A117"]["Lat"]
#以網(wǎng)點(diǎn)為原點(diǎn)，只看配送點(diǎn)與點(diǎn)之間的相對(duì)坐標(biāo)
a1.head()
            
          

            觀察配送點(diǎn)與?點(diǎn)的位置關(guān)系:

          

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

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

          

?

路線規(guī)劃?：基于點(diǎn)的?度順序配送

物流配送路徑優(yōu)化問(wèn)題是?個(gè)很經(jīng)典的問(wèn)題，針對(duì)該問(wèn)題有很多的解決?法。基于點(diǎn)的?度順序配 送是?個(gè)?較簡(jiǎn)單且運(yùn)?良好的算法。

            如上圖所?，P0為起始點(diǎn)，其它點(diǎn)為配送需求點(diǎn)。

          

1. 采?極坐標(biāo)來(lái)表?各點(diǎn)的相對(duì)位置，然后以P0點(diǎn)為坐標(biāo)原點(diǎn)，以P1為起始點(diǎn)，定其?度為零 度，以順時(shí)鐘或逆時(shí)鐘?向開(kāi)始掃描各個(gè)點(diǎn)，獲得各點(diǎn)與原點(diǎn)連線P0Pn相對(duì)于P0P1的?度? ?。

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

3. 掃描結(jié)束后獲得的點(diǎn)的序列就是各點(diǎn)的配送順序。?

了解了算法原理，我們來(lái)試驗(yàn)?下，A117這個(gè)?點(diǎn)的配送順序是如何的。

?

下?，就開(kāi)始路線規(guī)劃啦：

            
              a1=pd.concat([a1,a1.Lng/a1.Lat],axis=1) #計(jì)算各個(gè)配送點(diǎn)的正切值 a1.rename(columns={0:"zhengqie"},inplace=True)
a1=pd.concat([a1,(a1.Lng**2+a1.Lat**2)**0.5],axis=1)#計(jì)算各個(gè)配送點(diǎn)與中點(diǎn)的距離
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#加 了路徑長(zhǎng)度的計(jì)算

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()
            
          

            通過(guò)這份路線規(guī)劃圖，就不難明?配送?哥為何會(huì)繞遠(yuǎn)了。以順時(shí)針?向進(jìn)?配送 假設(shè)你在圖中1的位置， 配送?哥正在2的位置進(jìn)?配送， 按照實(shí)際距離來(lái)講，快遞?哥離你最近，下?個(gè)應(yīng)該?先為你進(jìn)?配送，但是根據(jù)?度??來(lái)規(guī)劃路線，快遞?哥卻去了更遠(yuǎn)的3這個(gè)位置！
          

            我餓著肚子癡癡地等待著我的牛肉飯，明明我是最近的，卻讓我白白地多等了半個(gè)小時(shí)，就因?yàn)槲壹业乩砦恢玫恼兄当葎e人家的大？這路線規(guī)劃一點(diǎn)兒也不合理！別急，我們來(lái)看看另一種路線規(guī)劃方法。
          

?

路線規(guī)劃?：環(huán)形掃描法

由于僅僅按照?度順序分配，導(dǎo)致徑向距離來(lái)回的浪費(fèi)。因此我們把點(diǎn)分為不同徑向長(zhǎng)度的環(huán)，環(huán)內(nèi)按照?度排序，減少?gòu)较??。

            
              def c1(a):#點(diǎn)與配送點(diǎn)的數(shù)據(jù)準(zhǔn)
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的負(fù)荷布置路徑
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) #數(shù)據(jù)處理
r0=p1.r.mean()#配送點(diǎn)與 點(diǎn)的平均距離
h0=p1[p1.r
              
            
          

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

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

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

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

          

想要獲取更多數(shù)據(jù)科學(xué)知識(shí)干貨，歡迎關(guān)注我們的公眾號(hào)【DC黑板報(bào)】

?

?

?