Google ORtool工具求解Vehicle Routing問(wèn)題

官方文檔鏈接：https://developers.google.com/optimization/routing

本翻譯文檔所有code（Apache 2.0 License）及圖片來(lái)自ortool官方文檔（Creative Commons Attribution 4.0 License），僅供學(xué)習(xí)使用，侵刪。

示例1：旅行商問(wèn)題（提供點(diǎn)與點(diǎn)之間的距離矩陣）

創(chuàng)造數(shù)據(jù)（目標(biāo)點(diǎn)之間的距離矩陣）-> 創(chuàng)建路徑規(guī)劃模型 -> 創(chuàng)建距離回調(diào)函數(shù) -> 設(shè)置旅行cost -> 設(shè)置搜索參數(shù) -> 求解 -> 輸出結(jié)果

示例一完整代碼：點(diǎn)此看代碼

示例二：電子板打孔（僅提供點(diǎn)的坐標(biāo)，使用函數(shù)計(jì)算歐拉距離）

創(chuàng)造數(shù)據(jù)（目標(biāo)點(diǎn)坐標(biāo)）-> 計(jì)算距離矩陣 -> 創(chuàng)建路徑規(guī)劃模型 -> 創(chuàng)建距離回調(diào)函數(shù) -> 設(shè)置旅行cost -> 設(shè)置搜索參數(shù) -> 求解 -> 輸出結(jié)果

示例二完整代碼：電子板打孔代碼

結(jié)果：（提供了兩種搜索策略）

示例三：車輛路徑規(guī)劃問(wèn)題（VRP）

四輛車從起點(diǎn)0出發(fā)，需遍歷所有點(diǎn)，求解使得四輛車中路徑最長(zhǎng)的那輛車長(zhǎng)度最短。

創(chuàng)造數(shù)據(jù)（距離矩陣 + 車輛數(shù)量 + 起點(diǎn)）-> 創(chuàng)建路徑規(guī)劃模型 ->? 創(chuàng)建距離回調(diào)函數(shù) ->? 添加距離維度 -> 設(shè)置旅行cost -> 設(shè)置搜索參數(shù) -> 求解 -> 輸出結(jié)果

示例三完整代碼：VRP代碼

示例四：帶容量限制的車輛路徑規(guī)劃問(wèn)題(CVRP)

在示例三的基礎(chǔ)上，四輛車有裝載容量限制，需要將放置在各個(gè)點(diǎn)的貨物運(yùn)回0號(hào)點(diǎn)，同樣是求解使得四輛車中路徑最長(zhǎng)的那輛車長(zhǎng)度最短。

創(chuàng)造數(shù)據(jù)（距離矩陣 + 車輛數(shù)量 + 起點(diǎn) + 車輛容量限制 + 每個(gè)點(diǎn)的貨物數(shù)量）-> 創(chuàng)建路徑規(guī)劃模型 ->? 創(chuàng)建距離回調(diào)函數(shù) ->? 添加需求回調(diào)函數(shù)和容量限制 -> 設(shè)置旅行cost -> 設(shè)置搜索參數(shù) -> 求解 -> 輸出結(jié)果

CVRP代碼：CVRP代碼

結(jié)果：

示例五：貨物運(yùn)輸?shù)能囕v路徑規(guī)劃問(wèn)題

需要規(guī)劃車輛路徑，使得車輛能夠?qū)⒛车氐呢浳镞\(yùn)輸?shù)搅硪粋€(gè)地方，同樣是求解使得四輛車中路徑最長(zhǎng)的那輛車長(zhǎng)度最短。

創(chuàng)造數(shù)據(jù)（距離矩陣 + 車輛數(shù)量 + 起點(diǎn) + 運(yùn)輸計(jì)劃）-> 創(chuàng)建路徑規(guī)劃模型 ->? 創(chuàng)建距離回調(diào)函數(shù) -> 設(shè)置旅行cost ->? 添加距離維度限制 -> 添加運(yùn)輸計(jì)劃 -> 設(shè)置搜索參數(shù) -> 求解 -> 輸出結(jié)果

完整代碼：pickup and delivery

示例六：VRPTW 有時(shí)間窗口限制的VRP問(wèn)題

訪問(wèn)的地點(diǎn)有時(shí)間窗口限制，時(shí)間窗口外的時(shí)間不可訪問(wèn)

創(chuàng)造數(shù)據(jù)（旅行時(shí)間矩陣 + 車輛數(shù)量 + 起點(diǎn) + 時(shí)間窗）-> 創(chuàng)建路徑規(guī)劃模型 ->? 創(chuàng)建旅行時(shí)間回調(diào)函數(shù) -> 設(shè)置旅行cost ->? 添加時(shí)間窗口限制? -> 設(shè)置搜索參數(shù) -> 求解 -> 輸出結(jié)果

完整代碼：VRPTW

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。