VRP（Vehicle Routing Problem）問題描述

在VRP問題中，假設(shè)有一個(gè)供求關(guān)系系統(tǒng)血当，車輛從倉(cāng)庫(kù)取貨翘贮，配送到若干個(gè)顧客處赊窥。車輛受到載重量的約束，需要組織適當(dāng)?shù)男熊嚶肪€狸页，在顧客的需求得到滿足的基礎(chǔ)上锨能，使代價(jià)函數(shù)最小。代價(jià)函數(shù)根據(jù)問題不同而不同芍耘，常見的有車輛總運(yùn)行時(shí)間最小址遇，車輛總運(yùn)行路徑最短等。

這個(gè)問題基于以下假設(shè)：

• 所有距離采用歐幾里得表示
• 每個(gè)顧客只接受一輛車的一次配送
• 從配送中心出發(fā)的車輛必須返回配送中心
• 每輛車載重量相同
• 一條路徑上顧客的總需求量不能超過車輛的最大載重量

定義為需要服務(wù)的兩個(gè)顧客編號(hào)齿穗，為配送中心的車輛編號(hào)傲隶，為顧客和倉(cāng)庫(kù)的集合饺律。
參數(shù)：

: 從顧客到顧客的行駛距離

：顧客的需求量

：車輛的最大載重量

決策變量：

：當(dāng)車輛被分配從顧客運(yùn)行到顧客時(shí)窃页，取1；否則取0

在給定了參數(shù)和定義了決策變量之后复濒，VRP問題可以用數(shù)學(xué)模型表示為：

VRP問題示例

給定車輛負(fù)載為400脖卖，各個(gè)節(jié)點(diǎn)的坐標(biāo)和需求如下(節(jié)點(diǎn)0為配送中心)：

遺傳算法求解VRP問題

個(gè)體編碼

對(duì)于個(gè)體采用自然數(shù)編碼，0代表配送中心巧颈，1--n代表顧客畦木；不同車輛的配送路線之間用0分隔（即每輛車都從倉(cāng)庫(kù)出發(fā)）；對(duì)于有n個(gè)顧客砸泛，k輛車的VRP問題來說十籍，染色體長(zhǎng)度為n+k+1。

例如配送中心有3輛車為8個(gè)客戶服務(wù)唇礁，一條可能的染色體如下：

0, 7, 0, 1, 2, 3, 5, 0, 8, 4, 6, 0

這條染色體表示的三輛車的行駛路線為:
第一輛車：0-7-0
第二輛車：0-1-2-3-5-0
第三輛車：0-8-4-6-0

解碼

利用分割符0勾栗，還原各條子路徑

交叉操作

參考了大連海事大學(xué)碩士學(xué)位論文《基于電動(dòng)汽車的帶時(shí)間窗的路徑優(yōu)化問題研究》中的交叉操作，生成新的個(gè)體盏筐，具體描述如下圖：

VRP問題交叉方法描述

突變操作

用2-opt算法對(duì)各條子路徑進(jìn)行局部?jī)?yōu)化

代碼示例

## 環(huán)境設(shè)定
import numpy as np
import matplotlib.pyplot as plt
from deap import base, tools, creator, algorithms
import random

params = {
    'font.family': 'serif',
    'figure.dpi': 300,
    'savefig.dpi': 300,
    'font.size': 12,
    'legend.fontsize': 'small'
}
plt.rcParams.update(params)

from copy import deepcopy
#-----------------------------------
## 問題定義
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) # 最小化問題
# 給個(gè)體一個(gè)routes屬性用來記錄其表示的路線
creator.create('Individual', list, fitness=creator.FitnessMin) 

#-----------------------------------
## 個(gè)體編碼
# 用字典存儲(chǔ)所有參數(shù) -- 配送中心坐標(biāo)围俘、顧客坐標(biāo)、顧客需求琢融、到達(dá)時(shí)間窗口界牡、服務(wù)時(shí)間、車型載重量
dataDict = {}
# 節(jié)點(diǎn)坐標(biāo)漾抬，節(jié)點(diǎn)0是配送中心的坐標(biāo)
dataDict['NodeCoor'] = [(15,12), (3,13), (3,17), (6,18), (8,17), (10,14),
                           (14,13), (15,11), (15,15), (17,11), (17,16),
                            (18,19), (19,9), (19,21), (21,22), (23,9),
                            (23,22), (24,11), (27,21), (26,6), (26,9),
                            (27,2), (27,4), (27,17), (28,7), (29,14),
                            (29,18), (30,1), (30,8), (30,15), (30,17)
                           ]
# 將配送中心的需求設(shè)置為0
dataDict['Demand'] = [0,50,50,60,30,90,10,20,10,30,20,30,10,10,10,
                      40,51,20,20,20,30,30,30,10,60,30,20,30,40,20,20]
dataDict['MaxLoad'] = 400
dataDict['ServiceTime'] = 1

def genInd(dataDict = dataDict):
    '''生成個(gè)體宿亡， 對(duì)我們的問題來說，困難之處在于車輛數(shù)目是不定的'''
    nCustomer = len(dataDict['NodeCoor']) - 1 # 顧客數(shù)量
    perm = np.random.permutation(nCustomer) + 1 # 生成顧客的隨機(jī)排列,注意顧客編號(hào)為1--n
    pointer = 0 # 迭代指針
    lowPointer = 0 # 指針指向下界
    permSlice = []
    # 當(dāng)指針不指向序列末尾時(shí)
    while pointer < nCustomer -1:
        vehicleLoad = 0
        # 當(dāng)不超載時(shí)纳令，繼續(xù)裝載
        while (vehicleLoad < dataDict['MaxLoad']) and (pointer < nCustomer -1):
            vehicleLoad += dataDict['Demand'][perm[pointer]]
            pointer += 1
        if lowPointer+1 < pointer:
            tempPointer = np.random.randint(lowPointer+1, pointer)
            permSlice.append(perm[lowPointer:tempPointer].tolist())
            lowPointer = tempPointer
            pointer = tempPointer
        else:
            permSlice.append(perm[lowPointer::].tolist())
            break
    # 將路線片段合并為染色體
    ind = [0]
    for eachRoute in permSlice:
        ind = ind + eachRoute + [0]
    return ind
#-----------------------------------
## 評(píng)價(jià)函數(shù)
# 染色體解碼
def decodeInd(ind):
    '''從染色體解碼回路線片段她混，每條路徑都是以0為開頭與結(jié)尾'''
    indCopy = np.array(deepcopy(ind)) # 復(fù)制ind烈钞，防止直接對(duì)染色體進(jìn)行改動(dòng)
    idxList = list(range(len(indCopy)))
    zeroIdx = np.asarray(idxList)[indCopy == 0]
    routes = []
    for i,j in zip(zeroIdx[0::], zeroIdx[1::]):
        routes.append(ind[i:j]+[0])
    return routes

def calDist(pos1, pos2):
    '''計(jì)算距離的輔助函數(shù)，根據(jù)給出的坐標(biāo)pos1和pos2坤按，返回兩點(diǎn)之間的距離
    輸入： pos1, pos2 -- (x,y)元組
    輸出： 歐幾里得距離'''
    return np.sqrt((pos1[0] - pos2[0])*(pos1[0] - pos2[0]) + (pos1[1] - pos2[1])*(pos1[1] - pos2[1]))

#
def loadPenalty(routes):
    '''輔助函數(shù)毯欣，因?yàn)樵诮徊婧屯蛔冎锌赡軙?huì)產(chǎn)生不符合負(fù)載約束的個(gè)體，需要對(duì)不合要求的個(gè)體進(jìn)行懲罰'''
    penalty = 0
    # 計(jì)算每條路徑的負(fù)載臭脓，取max(0, routeLoad - maxLoad)計(jì)入懲罰項(xiàng)
    for eachRoute in routes:
        routeLoad = np.sum([dataDict['Demand'][i] for i in eachRoute])
        penalty += max(0, routeLoad - dataDict['MaxLoad'])
    return penalty

def calRouteLen(routes,dataDict=dataDict):
    '''輔助函數(shù)酗钞，返回給定路徑的總長(zhǎng)度'''
    totalDistance = 0 # 記錄各條路線的總長(zhǎng)度
    for eachRoute in routes:
        # 從每條路徑中抽取相鄰兩個(gè)節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)距離并進(jìn)行累加
        for i,j in zip(eachRoute[0::], eachRoute[1::]):
            totalDistance += calDist(dataDict['NodeCoor'][i], dataDict['NodeCoor'][j])    
    return totalDistance

def evaluate(ind):
    '''評(píng)價(jià)函數(shù)来累，返回解碼后路徑的總長(zhǎng)度砚作，'''
    routes = decodeInd(ind) # 將個(gè)體解碼為路線
    totalDistance = calRouteLen(routes)
    return (totalDistance + loadPenalty(routes)),
#-----------------------------------
## 交叉操作
def genChild(ind1, ind2, nTrail=5):
    '''參考《基于電動(dòng)汽車的帶時(shí)間窗的路徑優(yōu)化問題研究》中給出的交叉操作，生成一個(gè)子代'''
    # 在ind1中隨機(jī)選擇一段子路徑subroute1嘹锁，將其前置
    routes1 = decodeInd(ind1) # 將ind1解碼成路徑
    numSubroute1 = len(routes1) # 子路徑數(shù)量
    subroute1 = routes1[np.random.randint(0, numSubroute1)]
    # 將subroute1中沒有出現(xiàn)的顧客按照其在ind2中的順序排列成一個(gè)序列
    unvisited = set(ind1) - set(subroute1) # 在subroute1中沒有出現(xiàn)訪問的顧客
    unvisitedPerm = [digit for digit in ind2 if digit in unvisited] # 按照在ind2中的順序排列
    # 多次重復(fù)隨機(jī)打斷葫录，選取適應(yīng)度最好的個(gè)體
    bestRoute = None # 容器
    bestFit = np.inf
    for _ in range(nTrail):
        # 將該序列隨機(jī)打斷為numSubroute1-1條子路徑
        breakPos = [0]+random.sample(range(1,len(unvisitedPerm)),numSubroute1-2) # 產(chǎn)生numSubroute1-2個(gè)斷點(diǎn)
        breakPos.sort()
        breakSubroute = []
        for i,j in zip(breakPos[0::], breakPos[1::]):
            breakSubroute.append([0]+unvisitedPerm[i:j]+[0])
        breakSubroute.append([0]+unvisitedPerm[j:]+[0])
        # 更新適應(yīng)度最佳的打斷方式
        # 將先前取出的subroute1添加入打斷結(jié)果，得到完整的配送方案
        breakSubroute.append(subroute1)
        # 評(píng)價(jià)生成的子路徑
        routesFit = calRouteLen(breakSubroute) + loadPenalty(breakSubroute)
        if routesFit < bestFit:
            bestRoute = breakSubroute
            bestFit = routesFit
    # 將得到的適應(yīng)度最佳路徑bestRoute合并為一個(gè)染色體
    child = []
    for eachRoute in bestRoute:
        child += eachRoute[:-1]
    return child+[0]

def crossover(ind1, ind2):
    '''交叉操作'''
    ind1[:], ind2[:] = genChild(ind1, ind2), genChild(ind2, ind1)
    return ind1, ind2

#-----------------------------------
## 突變操作
def opt(route,dataDict=dataDict, k=2):
    # 用2-opt算法優(yōu)化路徑
    # 輸入：
    # route -- sequence领猾，記錄路徑
    # 輸出： 優(yōu)化后的路徑optimizedRoute及其路徑長(zhǎng)度
    nCities = len(route) # 城市數(shù)
    optimizedRoute = route # 最優(yōu)路徑
    minDistance = calRouteLen([route]) # 最優(yōu)路徑長(zhǎng)度
    for i in range(1,nCities-2):
        for j in range(i+k, nCities):
            if j-i == 1:
                continue
            reversedRoute = route[:i]+route[i:j][::-1]+route[j:]# 翻轉(zhuǎn)后的路徑
            reversedRouteDist = calRouteLen([reversedRoute])
            # 如果翻轉(zhuǎn)后路徑更優(yōu)米同，則更新最優(yōu)解
            if  reversedRouteDist < minDistance:
                minDistance = reversedRouteDist
                optimizedRoute = reversedRoute
    return optimizedRoute

def mutate(ind):
    '''用2-opt算法對(duì)各條子路徑進(jìn)行局部?jī)?yōu)化'''
    routes = decodeInd(ind)
    optimizedAssembly = []
    for eachRoute in routes:
        optimizedRoute = opt(eachRoute)
        optimizedAssembly.append(optimizedRoute)
    # 將路徑重新組裝為染色體
    child = []
    for eachRoute in optimizedAssembly:
        child += eachRoute[:-1]
    ind[:] = child+[0]
    return ind,

#-----------------------------------
## 注冊(cè)遺傳算法操作
toolbox = base.Toolbox()
toolbox.register('individual', tools.initIterate, creator.Individual, genInd)
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
toolbox.register('evaluate', evaluate)
toolbox.register('select', tools.selTournament, tournsize=2)
toolbox.register('mate', crossover)
toolbox.register('mutate', mutate)

## 生成初始族群
toolbox.popSize = 100
pop = toolbox.population(toolbox.popSize)

## 記錄迭代數(shù)據(jù)
stats=tools.Statistics(key=lambda ind: ind.fitness.values)
stats.register('min', np.min)
stats.register('avg', np.mean)
stats.register('std', np.std)
hallOfFame = tools.HallOfFame(maxsize=1)

## 遺傳算法參數(shù)
toolbox.ngen = 400
toolbox.cxpb = 0.8
toolbox.mutpb = 0.1

## 遺傳算法主程序
## 遺傳算法主程序
pop,logbook=algorithms.eaMuPlusLambda(pop, toolbox, mu=toolbox.popSize, 
                                      lambda_=toolbox.popSize,cxpb=toolbox.cxpb, mutpb=toolbox.mutpb,
                   ngen=toolbox.ngen ,stats=stats, halloffame=hallOfFame, verbose=True)

輸出計(jì)算結(jié)果：

from pprint import pprint

def calLoad(routes):
    loads = []
    for eachRoute in routes:
        routeLoad = np.sum([dataDict['Demand'][i] for i in eachRoute])
        loads.append(routeLoad)
    return loads

bestInd = hallOfFame.items[0]
distributionPlan = decodeInd(bestInd)
bestFit = bestInd.fitness.values
print('最佳運(yùn)輸計(jì)劃為：')
pprint(distributionPlan)
print('最短運(yùn)輸距離為：')
print(bestFit)
print('各輛車上負(fù)載為：')
print(calLoad(distributionPlan))

# 畫出迭代圖
minFit = logbook.select('min')
avgFit = logbook.select('avg')
plt.plot(minFit, 'b-', label='Minimum Fitness')
plt.plot(avgFit, 'r-', label='Average Fitness')
plt.xlabel('# Gen')
plt.ylabel('Fitness')
plt.legend(loc='best')

# 計(jì)算結(jié)果
#最佳運(yùn)輸計(jì)劃為：
#[[0, 9, 12, 19, 22, 24, 25, 17, 0],
# [0, 6, 4, 3, 2, 1, 5, 0],
# [0, 7, 0],
# [0, 8, 10, 11, 13, 14, 16, 18, 23, 26, 30, 29, 28, 27, 21, 20, 15, 0]]
#最短運(yùn)輸距離為：
#(136.93713103610511,)
#各輛車上負(fù)載為：
#[200, 290, 20, 391]

迭代過程如下圖所示：

VRP_iterations

總共使用了4輛車，各自的行駛路徑如下：

VRP_routes