帶有協(xié)作機(jī)制的車輛路徑問題的分支定價(jià)算法.pdf

1、近年來,隨著全球化步伐的加快和國際貿(mào)易的迅猛增長,運(yùn)輸環(huán)節(jié)已經(jīng)成為全球供應(yīng)鏈中至關(guān)重要的一環(huán)。對(duì)于許多公司來說,分銷貨物所需的運(yùn)輸費(fèi)用在整個(gè)運(yùn)作成本中占有相對(duì)高的比例。如何有效地減少運(yùn)輸費(fèi)用成為了工業(yè)界和理論界共同關(guān)注的課題。
　　 本文中,我們把協(xié)作機(jī)制引入到車輛路徑問題中,提出了帶有協(xié)作機(jī)制的車輛路徑問題。通過協(xié)作,各個(gè)公司之間可以共享車輛容量,消除重復(fù)、對(duì)流路徑,從而達(dá)到減少運(yùn)輸費(fèi)用,提高整體運(yùn)作效率的目的。
　　

2、 本文主要研究了傳統(tǒng)的車輛路徑問題(VRP)和面向收益的車輛路徑問題(MVR.PP),并在第一章里對(duì)其基本概念、主要分類和研究現(xiàn)狀作出了詳細(xì)介紹。
　　 本文介紹了VRP的精確算法,給出了一個(gè)以行駛距離最小為目標(biāo)的混合整數(shù)規(guī)劃模型,通過Danzig-wolfe分解,把該模型轉(zhuǎn)化成了集合劃分(SP)模型和子問題模型。該子問題模型是一類帶有資源約束的最短路徑問題(RCESPP),可以通過雙向動(dòng)態(tài)規(guī)劃算法來求解。實(shí)驗(yàn)表明,在較大規(guī)模算

3、例中,該算法能夠在可接受的時(shí)間內(nèi)求得最優(yōu)解。
　　 針對(duì)帶有協(xié)作機(jī)制的VRP,本文提出了其分支定價(jià)算法。根據(jù)該問題的特點(diǎn),建立了SP模型和子問題模型。為了減少計(jì)算時(shí)間,我們對(duì)原有的動(dòng)態(tài)規(guī)劃算法進(jìn)行了改進(jìn),提出了“一次擴(kuò)展+多次拼接”的思想。通過大量實(shí)驗(yàn)數(shù)據(jù)表明,加入“協(xié)作聯(lián)盟”能夠有效地減少企業(yè)個(gè)體和聯(lián)盟整體的運(yùn)輸費(fèi)用,對(duì)加強(qiáng)企業(yè)競爭力具有很大幫助；還提出了協(xié)作關(guān)系穩(wěn)定性的概念,并對(duì)協(xié)作關(guān)系的穩(wěn)定性進(jìn)行了數(shù)值分析。
　　

4、 第五章對(duì)MVRPP和帶有協(xié)作機(jī)制的MVRPP進(jìn)行了研究。在MVRPP中,包括兩個(gè)相互沖突的目標(biāo):收益最大和行駛距離最短。通過把行駛距離作為約束來考慮,該問題被轉(zhuǎn)化為一個(gè)單目標(biāo)規(guī)劃問題。針對(duì)MVRPP,本文提出了以收益最大為目標(biāo)的SP模型,并給出了求解RCESPP的雙向動(dòng)態(tài)規(guī)劃算法。同時(shí),本文還對(duì)帶有協(xié)作機(jī)制的MVRPP進(jìn)行了探究,提出了該問題的數(shù)學(xué)模型,并根據(jù)帶有協(xié)作機(jī)制的MVRPP問題的特點(diǎn),設(shè)計(jì)了雙向動(dòng)態(tài)規(guī)劃算法。數(shù)值實(shí)驗(yàn)表明,加