1、摘 要摘 要隨著社會市場經(jīng)濟的發(fā)展，物流對經(jīng)濟活動的影響越來越 明顯，對國民經(jīng)濟的發(fā)展起著舉足輕重的作用。車輛路徑問題一直是物流配送活動中的最基本的問題之一，由于其應(yīng)用的廣泛性和明顯的經(jīng)濟效益，一直受到國內(nèi)外學者的廣泛關(guān)注。因此研究車輛路徑問題的實用、有效的優(yōu)化方法，對于促進物流配送、智能交通、運輸調(diào)度等領(lǐng)域的發(fā)展具有重要的理論意義和實際意義，將會獲得巨大的社會效益和經(jīng)濟效益.本文在全面、系統(tǒng)研究車輛路徑問題的基礎(chǔ)上，主要針對實際需求，

2、 研究了目前最常見、物流發(fā)展迫切需要解 決的幾種車輛路徑問題，給 出了相應(yīng)的求解方法。本文首先對車輛路徑問 題的提法、基本概念、 研究的發(fā)展和現(xiàn)狀進行了系統(tǒng)、 詳細的介紹。 然后，主要對以下四 種問題進行了深入研究:1 . 研究了隨機需求的多車輛 路徑 問題 ( MV R P S D)，給出了求解路徑長度受限的MV R P S D問題的兩種實際可行的求解算法， 在路徑行駛費用的計算中引入了“ 預(yù)先”裝載方式，避免了現(xiàn)行算法中因車上貨物量

3、不足而造成的對顧客重復(fù)送貨、從而造成行駛費用增加的問題，并使算法的運行時間在可接受的范圍內(nèi)。仿真實驗表明本文提出的預(yù)優(yōu)化算法和重優(yōu)化算法與其它同類算法相比， 不僅克服了 上述缺點、更符合當 前的實際需求， 而且求解效率也明顯提高。 2 . 根據(jù)實際需求， 對傳統(tǒng)的單車場帶回程車輛路徑問題進行了擴展， 提出并研究了具有約束的、 帶回程的多車場路徑優(yōu)化問題 ( MD V R P B ) ， 給出了一套完整的優(yōu)化求解方法和根據(jù) 問題特征改進

4、方法的實施策略。 該方法給出的結(jié)果不僅可以極大的節(jié)約行駛費用，而且極大地提高了運算效率。仿真實驗表明， 在多車場、 多車輛路徑問 題中， 引入車輛的回程運輸可以極大的節(jié)約行駛費用， 也證明了 本文算法的有效性。 3 . 研究了 同時取送貨的車輛路徑問 題 ( V R P S P D )，提出了同時取送貨的車輛路徑優(yōu)化問題的算法。根據(jù)車輛的 剩余容量和顧客的凈裝載量對于路徑構(gòu)造的影響， 建立了一種直觀的V R P S P D問 題的數(shù)

5、學模型， 提出了一種基于凈裝載量的 插入準則。 插入準則充分考慮了 顧客的凈裝載量和車輛的 剩余空間， 能夠使車輛路徑構(gòu)造有更大的自由度，方便后續(xù)顧客插入到路徑中。因此，與其它插入準則相比，該方Ab s t r a c tAb s t r a c tWi t h t h e d e v e l o p me n t o f m a r k e t e c o n o m y , l o g i s t i c s h a

6、v e e v i d e n t i m p a c t o ne c o n o m y a c t i v i t y a n d p l a y a n i m p o r t a n t r o l e i n c o u n t r y e c o n o m y d e v e l o p me n t .V e h i c l e r o u t i n g p r o b l e m i

7、 s o n e o f t h e m o s t b a s i c a n d i m p o r t a n t p r o b l e m s i n l o g i s t i c sd i s t r i b u t i o n a c t i v i t i e s , a n d a t t r a c t t h e r e s e a r c h e r s ' a t e

8、n t i o n o f d o m e s t i c a n d o v e r s e a sb e c a u s e o f t h e e x t e n s i v e a p p l i c a t i o n a n d o b v i o u s e c o n o m y b e n e f i t . S o s t u d y i n ga p p l i e d a n d

9、e f i c i e n t o p t i m a l a l g o r i t h m s f o r v e h i c l e r o u t i n g p r o b l e m h a s i m p o r t a n ta c a d e m i c a n d a c t u a l m e a n i n g f o r t h e d e v e l o p me n t o f

10、 l o g i s t i c s d i s t r i b u t i o n , i n t e l l i g e n tt r a f f i c a n d t r a n s p o r t a t i o n s c h e d u l e , a n d w i l l o b t a i n t r e m e n d o u s s o c i e t y a n d e c o n o

11、 m yb e n e f i t . A c c o r d i n g t o t h e a c t u a l r e q u i r e m e n t , t h i s t h e s i s m a i n l y f o c u s o n t h e s t u d y i n go f t h e m o s t f a m i l i a r a n d e x i g e n

12、t v e h i c l e r o u t i n g p r o b l e ms o n t h e b a s i s o f t h e g e n e r a la n d s y s t e mi c r es e a r c h , a n d p r o p o s e s t h e c o r r e s p o n d i n g s o l v i n g a l g o r

13、 i t h m f o r t h ep r o b l e m s .F i r s t l y t h i s t h e s i s i n t r o d u c e s t h e b a s i c c o n c e p t a n d r es e a r c h s t a t u s f o r v e h i c l er o u t i n g p r o b l e m s y

14、s t e m i c a l l y a n d d e t a i l e d l y . S e c o n d l y , t h e f o l l o w i n g f o u r m a i nc o n t e n t s a r e i n v e s t i g a t e d : 1 . S t u d y t h e m u l t i p l e v e h i c l e s

15、r o u t i n g p r o b l e m w i t hs t o c h a s t i c d e m a n d ( MV R P S D ) a n d p r o p o s e t w o p r a c t i c a l l y f e a s i b l e a l g o r i t h m s f o rt r a v e l i n g d i s t a n c e r

16、e s t r i c t e d MV R P S D . I n t h e c o m p u t a t i o n o f e x p e c t e d t r a v e l i n g c o s t ,t h e o p t i m a l r e s t o c k i n g p o l i c y i s t a k e n i n t o a c c o u n t t o a

17、 v o i d d e l i v e r i n g g o o d sr e p e a t e d l y a n d i n c r e a s i n g t r a v e l i n g c o s t b e c a u s e o f t h e r e m a i n i n g s t o c k i n t h e v e h i c l eb e i n g i n s u f

18、i c i e n t t o s a t i s f y d e m a n d u p o n a r r i v a l a t a c u s t o m e r l o c a t i o n i n m o s t a c t u a la l g o r i t h m s . T h e a l g o r i t h m s r u n i n a c c e p t a b l e

19、 t i m e . T h e c o m p u t a t i o n r e s u l t s i n d i c a t et h a t t h e a p r i o r i a l g o r i t h m a n d t h e r e o p t i m i z a t i o n a l g o r i t h m i n t h i s t h e s i s n o t o

20、 n l yo v e r c o me t h e a b o v e d e f e c t s , b u t a l s o h a v e b e t t e r v a l i d i t y a n d a d a p t a b i l i t y c o m p a r e dw i t h o t h e r s i mi l a r a l g o r i t h m s . 2 .

21、 A c c o r d i n g t o a c t u a l r e q u i r e me n t , e x t e n d t h et r a d i t i o n a l s i n g l e - d e p o t v e h i c l e r o u t i n g p r o b l e m w i t h c o n s t r a i n e d b a c k h a u l

22、 s , a n dp r o p o s e a n i n t e g r a t e d o p t i m a l a l g o r i t h m a n d s e v e r a l r e d u c t i o n c o m p u t a t i o n p o l i c i e s t od e a l w i t h m u l t i - d e p o t s v e h i

23、 c l e r o u t i n g p r o b l e m w i t h c o n s t r a i n e d b a c k h a u l s . T h eo u t c o me o f t h i s a l g o r i t h m c a n s a v e mu c h t r a v e l i n g c o s t a n d i m p r o v e t h