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

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

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

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

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