先說TSP吧,在壹個平整表面,有若幹個點,任意兩點間均可到達,我們的旅行商現在正在0點處,他想順次走完所有的點,而且壹個點不想走兩遍,最後回到0點,求怎麽走總路徑最短。
CVRP類似,平面內由壹系列顧客點(costumer),以及壹個車場(depot),壹系列車輛想從車場出發不重不漏地訪問所有顧客點最後回到車場。與TSP不同的是,每個顧客點都有壹個可量化的需求,而每輛車能滿足需求的能力有限,比如顧客點是消費者,車場是快遞站,快遞員從快遞站出發為消費者送快遞,但是快遞員每次能拿的貨是有限的,就需要好多快遞員同時從快遞站點出發,每個快遞員訪問壹系列不同的消費者,最後回到快遞站點。求怎麽走總路徑最短。