某網(wǎng)上銷(xiāo)售公司現(xiàn)收到12個(gè)客戶(hù)的訂貨請(qǐng)求,客戶(hù)的位置及訂貨規(guī)模見(jiàn)表。該公司送貨部門(mén)有5輛卡車(chē),卡車(chē)最大裝載量均為225件。試用節(jié)約法為該公司設(shè)計(jì)合理的運(yùn)輸方案,并說(shuō)明每種方案的車(chē)輛行駛總路程。
(1)客戶(hù)及配送中心之間的距離
某批發(fā)中心每天要為城區(qū)21個(gè)零售店客戶(hù)送貨,客戶(hù)的位置信息和需求信息見(jiàn)下表。一年按250個(gè)營(yíng)業(yè)日考慮;該地區(qū)公路網(wǎng)完善,沒(méi)有河流、湖泊或其他需要繞行的障礙。目前公司有5輛送貨車(chē),每輛車(chē)可裝500箱貨物。
要求:
(1)用掃描法確定所需的運(yùn)貨卡車(chē)數(shù)量;
(2)確定每輛卡車(chē)的最佳運(yùn)輸路線(xiàn)及客戶(hù)服務(wù)順序。
有一配送中心向某一客戶(hù)送貨,其行車(chē)可能途經(jīng)6個(gè)地點(diǎn),如圖所示,點(diǎn)1是配送中心位置,點(diǎn)8是客戶(hù)位置,其他為中途可經(jīng)過(guò)的點(diǎn),箭頭上的數(shù)代表兩點(diǎn)間距離(KM)。求配送中心到客戶(hù)的最短距離和最佳行車(chē)路線(xiàn)。(提示:可用Dijkstra方法求解)
最短路徑是:從節(jié)點(diǎn)1→4→7→5→8, 總長(zhǎng)度為10。