問題描述
給定10w輛出租車的經(jīng)緯度和車廂乘客終點(diǎn)场斑，并給定一個(gè)乘客的起止位置，找出繞路不超過10km且距離乘客不超過10km的最多五輛車颈走。
方法
實(shí)現(xiàn)分成三步：
- 預(yù)處理階段：預(yù)處理出一輛車上任意兩人距離这揣，以及每輛車將乘客依次送達(dá)目的地的路程D1涝开；
- 遍歷出租車穗酥，篩去離乘客距離超過10km的出租車护赊；
- 剩下的出租車，計(jì)算接乘客路程D2,砾跃、接到乘客后依次送達(dá)的距離D3骏啰、待接乘客離自己目的地的最短距離D4。然后計(jì)算繞路距離抽高，不超過10km的留下判耕。
在實(shí)現(xiàn)中，使用metis庫計(jì)算路網(wǎng)中的數(shù)據(jù)厨内，包括建樹和計(jì)算兩點(diǎn)間最短距離祈秕。
完成功能
- 輸入一個(gè)乘客位置，在可以忍受的時(shí)間內(nèi)返回不超過5個(gè)有空位的出租車雏胃。所有返回的出租車與乘客距離不超過10km，若沒有合適的出租車志鞍，則返回空列表瞭亮；
- 返回的所有出租車的繞路距離不超過10km；
- 提供UI界面方便輸入輸出的交互固棚；
- 使用路網(wǎng)數(shù)據(jù)完成大作業(yè)统翩；
- （加分項(xiàng)） 給出建議路線。
運(yùn)行方式
使用的第三方庫為metis和Qt此洲。請(qǐng)使用qmake或Qt Creator運(yùn)行程序厂汗。程序界面如下：
image.png
圖中右側(cè)輸入乘客起止坐標(biāo)，點(diǎn)擊search按鈕即可獲得最近的滿足條件的（最多）五輛出租車呜师。下面列出了五輛車的ID和距離乘客的距離娶桦，以及給該出租車規(guī)劃的路線。點(diǎn)擊show按鈕即可查看規(guī)劃路線汁汗，其中綠點(diǎn)表示乘客的起始坐標(biāo)衷畦，紅點(diǎn)表示乘客的終止坐標(biāo)；深橙色的點(diǎn)表示出租車的位置知牌，淺橙色的點(diǎn)為車上所有乘客的下車坐標(biāo)祈争。藍(lán)色為路線。
