帶可選時(shí)間窗的車(chē)輛調(diào)度多目標(biāo)優(yōu)化方法

文/黃埔生 曾強(qiáng)

1.引言

車(chē)輛調(diào)度問(wèn)題（Vehicle Routing Problem,VRP）最早由學(xué)者Dantzig和Ram ser于1959年提出，其一般定義如下[1]：對(duì)一系列裝貨點(diǎn)和卸貨點(diǎn)，組織適當(dāng)?shù)男熊?chē)路線，使車(chē)輛有序地通過(guò)它們，在滿足一定的約束條件下，達(dá)到一定的目標(biāo)。車(chē)輛調(diào)度的優(yōu)化目標(biāo)有很多，大致可分為兩類：一類是有利于物流企業(yè)的目標(biāo)，如配送路程最短[2]、配送成本最低[3]、配送車(chē)輛最少[4]；另一類是有利于客戶的目標(biāo)，如延遲時(shí)間最短[5]、滿意度最高[6]等。其中，配送成本和客戶滿意度是兩個(gè)最根本、最重要的優(yōu)化目標(biāo)。送貨的準(zhǔn)時(shí)性是決定客戶滿意度的核心因素之一。在此背景下，帶時(shí)間窗約束的車(chē)輛調(diào)度問(wèn)題（Vehicle Routing Problem w ith Time W indow s,VRPTW）成為一個(gè)重要研究課題。多目標(biāo)車(chē)輛調(diào)度問(wèn)題屬于NP-hard問(wèn)題。常用的多目標(biāo)優(yōu)化方法有“間接法”和“直接法”兩種。間接法是將多目標(biāo)轉(zhuǎn)換為單目標(biāo)、再采用單目標(biāo)優(yōu)化法進(jìn)行求解的方法，該方法的缺點(diǎn)是受人工干擾因素較大且不能得到一個(gè)完整的Pareto解集以供決策[13]。NSGA算法于1994年被Srim ivas和Deb提出[7]，其優(yōu)點(diǎn)包括非劣最優(yōu)解均勻分布、優(yōu)化目標(biāo)數(shù)可以任意選擇[8]。文獻(xiàn)[9-10]通過(guò)對(duì)以上方法定量研究得出“NSGA算法性能優(yōu)于其他算法”的結(jié)論。2002年，Deb[11]在NSGA的基礎(chǔ)上又提出了帶精英策略的非支配排序遺傳算法（NSGA II），大大提高了NSGA算法的性能。基于以上分析，本文針對(duì)一類帶可選時(shí)間窗的車(chē)輛調(diào)度問(wèn)題，提出了一種基于NSGA II算法的多目標(biāo)優(yōu)化方法。

2.問(wèn)題描述

某配送中心0服務(wù)于n個(gè)客戶，為其配送某種貨物。假設(shè)條件：①車(chē)輛完成配送后需回到配送中心；……