Time and reliability in vehicle routing problems
Başlık çevirisi mevcut değil.
- Tez No: 401361
- Danışmanlar: PROF. DR. TOM VAN WOENSEL, DR. NICO DELLAERT, DR. TON DE KOK
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Technische Universiteit Eindhoven
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 157
Özet
Özet yok.
Özet (Çeviri)
Carrier companies daily deal with the transportation problem of delivering goods to customers in a cost-effective manner. The Vehicle Routing Problem (VRP) basically captures this regular task. The VRP involves finding a set of feasible routes, starting from and ending at a given depot, to fulfill the demand of a number of customers located in a small area (e.g., a county or a city). The distances between each pair of customers and between all customers and the depot are known. The objective is to minimize the total cost, which is usually a function of the total distance traveled or the number of vehicles used or a combination of these. Each vehicle, which belongs to a homogeneous fleet of equal capacity, covers a route. In each route, customers are visited exactly once by the vehicle assigned and the total demand delivered cannot exceed the vehicle capacity. The VRP belongs to the class of NP-hard combinatorial optimization problems since it contains the traveling salesman problem as a special case. In the literature, there exists a wide variety of solution procedures developed for the VRP and its variants. The classical VRP is enhanced by incorporating a customer service aspect, i.e., starting the service at each customer within a given time interval, resulting in the Vehicle Routing Problem with TimeWindows (VRPTW). In the VRPTW, the service at each customer is provided within its predefined time window with respect to the deterministic arrival time moment of the vehicle assigned. This problem assumes that customers have hard time windows where violations are not permitted. More specifically, vehicles wait with no cost if they arrive early and they cannot serve if they arrive late. In real-life applications, carrier companies are confronted with several other features which are typically not considered in the VRP and in the VRPTW. The research conducted in this thesis introduces a number of realistic VRP and VRPTW variations to reflect these features. Both exact and approximate algorithms are constructed to solve the variations proposed. Stochastic variants of the VRP and of the VRPTW appear in case some elements considered in the classical formulations are random. In practice, the role of stochasticity is important in travel times, demands and customers. The research area of stochastic variants is relatively recent compared to the other versions and it is progressing fast. In Chapter 2, we present a review of the literature on stochastic vehicle routing problems. The purpose of this chapter is to survey the main versions studied and the main solution procedures developed for these versions. Most solution methods proposed for the stochastic variants are metaheuristics. Significant progress has been observed in the development of these approximate algorithms. In Chapter 2, we mainly focus on presenting metaheuristic solution methods. In real-life applications, carrier companies are faced with a traffic network which has different levels of congestion. Congestion leads to fluctuations in speed and thus in travel times. In this thesis, stochastic travel times are considered in Chapters 3 and 4, and both stochastic and time-dependent travel times are considered in Chapter 5. The research conducted in these chapters addresses the time perspective employed in the VRP. In case of considering time windows, both early and late servicing are (usually) possible in practice with some penalty costs. Mathematically, this is translated into soft time windows in the formulations. In this thesis, the service quality (whether the vehicle arrives within the time window or not) is evaluated by using a rich set of measures where the features observed in real-life applications are taken into account. In Chapters 3, 4 and 5, customers have soft time windows. In Chapter 6, the delivery measures are computed with respect to the flexible time windows that are obtained by relaxing the hard time windows by a given (customer specific) tolerance. The research conducted in these chapters addresses the reliability perspective for the VRP and the VRPTW. Chapter 3 considers stochastic travel times (with a known probability distribution) for a VRP with soft time windows. A model is proposed which is the first formulation that distinguishes between transportation costs and service costs. The objective is to obtain solutions, which are cost-efficient for carrier companies and reliable for customers. Due to the complexity of the problem studied, we develop an effective approximation procedure based on Tabu Search metaheuristic. We experiment with well-known problem instances where their deterministic optimal/best-known solutions have been reported in the literature. Chapter 3 shows that these solutions considerably deteriorate once applied in a stochastic environment and it is not beneficial to use them even as initial solutions. Moreover, the Tabu Search procedure generates solutions that perform well in various network structures (especially when we start with the routes obtained by the initialization algorithm proposed in Chapter 3). We observe meaningful combinations of transportation costs and service costs in the solutions. For carrier companies, the proposed model also provides the advantage of a significant reduction in service costs by having a small increase in transportation costs where the same number of vehicles is used. In Chapter 4, we develop the first exact solution procedure for the VRP with stochastic travel times and soft time windows. This algorithm, which is based on column generation and branch-and-price, provides solutions where the efficiency and the reliability have equal importance. A new dominance relation is introduced to be implemented in the pricing subproblem of the column generation algorithm. As we consider soft time windows (include no resource constraint) and stochastic travel times, this dominance relation and thus the pricing subproblem are rather complex. In the branch-and-price tree, depth-first search and breadth-first search methods are separately employed. Results show that the medium- to large-sized problems are effectively solved by the exact procedure proposed. Chapter 5 extends the time dimension of the VRP by considering both stochastic and time-dependent travel times. Having soft time windows for the deliveries incorporates a customer service dimension. This chapter validates the model and the solution methodology introduced in Chapter 3 for a stochastic and time-dependent environment. In addition to the adjusted Tabu Search procedure, an Adaptive Large Neighborhood Search is implemented to solve the model addressed. Depending on whether service times are included or not, we consider two versions of this problem. Experiments confirm that the proposed procedure is very effective to obtain solutions, which perform well in a stochastic and time-dependent network. Since the distributions of the arrival times are now approximated, we evaluate the quality of the solutions by simulation. Results confirm that the distributions of the arrival times and thus the related expected values are reliably estimated in this chapter. Furthermore, the resulting solutions are compared to (i) those reported in the literature for the classical VRPTW where travel times are deterministic and time-independent, (ii) those generated in Chapter 3 where travel times are stochastic and time-independent. In many instances, the deterministic optimal/best-known solutions perform poorly in the network, which is a close representation of real-life applications. Solutions obtained for the problem with stochastic (but time-independent) travel times are relatively good; however, they can still be improved with respect to time-dependency. In Chapter 6, the concept of flexible time windows is defined and incorporated into the VRP. The resulting problem is denoted as the VRPFlexTW. Time windows in this problem allow early and late servicing to a certain extent with some penalty costs. The objective is to minimize the total cost which involves traveling costs, fixed costs of vehicles used for service, and penalty costs. The solution approach combines a Tabu Search metaheuristic with a linear programming model. In the latter model, the optimal departure times of each vehicle from the depot and from each customer in its route are obtained. The conducted experiments compare VRPFlexTW to VRPTW where customers have hard time windows (allow no early or late servicing). Results show that VRPFlexTW leads to operational gains in many problem instances with respect to the solutions obtained for the classical VRPTW. These gains are observed as a reduction in the total distance traveled or as a reduction in the number of vehicles used or as a reduction in both. Furthermore, we have a reduction both in the average total distance traveled and in the average number of vehicles as the flexibility of the time windows increases.
Benzer Tezler
- Kargo taşımacılığı sektöründe son adım dağıtım planlama ve rota optimizasyonu
Last mile delivery planning and route optimization in cargo transportation
SELİN BOSTAN
Yüksek Lisans
Türkçe
2023
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
DOÇ. DR. CANER GÜNEY
- Çoklu insansız hava araçları arası altyapısız ağlar için yeni bir konum bilgisi paylaşımlı ve yönlü ortam erişim kontrol protokolü
A novel location oriented directional medium access control protocol for ad hod unmanned air vehicle networks
ŞAMİL TEMEL
Doktora
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHava Harp Okulu KomutanlığıBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. İLKER BEKMEZCİ
- Impact of inter-vehicular communication performance on different traffic mobility models: A case study of Ad Hoc on-Demand distance vector routing protocol
Farklı trafik hareketlilik modeli üzerinde araç içi iletişim performansına etkiler: İsteğe bağlı isteğe bağlı mesafe vektör yönlendirme protokolü üzerine bir vaka çalışması
TAOFEEK ABIODUN OLASUNKANMI YUSUF
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DENİZ TURGAY ALTILAR
- Esnek imalat sistemleri ve alternatif rotaları göz önünde bulundurarak esnek ortamlar için üretim hücrelerinin dizaynı
Flexible manufacturing systems and design of manufacturing cells for flexible environmental
GİRAY İLKER ÇELİK
Yüksek Lisans
Türkçe
1994
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. GÖNÜL YENERSOY