Vehicle scheduling problem with sequence dependent trips
- Global styles
- Apa
- Bibtex
- Chicago Fullnote
- Help
Abstract
Bu çalışmada, biz sıralı bağımlı sefer zamanlarına sahip araç çizelgeleme problemi üzerineçalıştık. Problem, araçların sabit başlama ve bitiş zamanına sahip seferlere minimum maliyetile atanması problemidir. Seferler arasındaki sefer süresi deterministlik olarak bilinmektedir.Taşıma yapabilecek, farklı kapasiteye, sabit ve değişken maliyetine sahip araç çeşitlerimevcuttur. Normal ve fazla kullanımlarındaki kullanım maliyeti araç tiplerine göredeğişmektedir. Problem yapı bakımından başlama ve bitiş zamanları bilinen ve amaçfonksiyonu bütün işleri yapacak araç kullanım maliyetinin minimum olacağı taktiksel sabit işçizelgeleme problemine benzemektedir. Eğer işin başlama zamanında uygun bir makine yoksaiş yapılamaz.Problem Tam Sayılı Programlama Modeli kullanılarak formüle edilmiştir. Araçlarınnormal sürede kullanımları yaygınlık zamanı kısıtı kullanılarak belirtilmiştir. Probleminmatematiksel modeli LINGO 8.0 ve GAMS 20.2 CPLEX çözücü kullanılarak modellenmiştir.Problemin kompleks yapısı yüzünden orta hacimdeki problemlerde bile optimum çözümünbulunması çok zaman almaktadır. Bu yüzden fazla kullanıma dayalı ikişer değişik çözümtipinde üç farklı sezgisel yaklaşım geliştirilmiştir. Algoritmalar DEV C++ derleyicisikullanılarak C programlama dilinde kodlanmıştır. Algoritmaların ortalama performanslarınınbulunması için örnek denemeler yaratılmıştır. Çeşitli yöntemlerle ve GAMS programıkullanılarak problemin performansını değerlendirmede kullanılacak alt limitler bulunmayaçalışılmıştır. Problemin sefer sayısı yüzden fazla olan denemelerde bile sezgisel yöntemkullanılarak çok kısa sürede çözüldüğü gösterilmiştir. Problem için, sezgisel yöntemlebulunan çözümlerin en küçüğünün optimum çözümden ortalama % 10 büyük olduğugösterilmiştir.Anahtar Kelimeler: Taktiksel Sabit İş Çizelgelemesi, Yaygınlık Zamanı Kısıtları, TamsayılıProgramlama, Sezgiseller In this study, we consider a vehicle scheduling problem with sequence dependent triptimes. The problem is assigning vehicles to a set of trips with fixed ready times and deadlines,while minimizing cost. The trip time for a vehicle between any two places is also knowndeterministically. A number of different types of vehicles are available for transportation,each with different capacities, fixed and variable costs. The costs for regular and overtimeutilization also vary for different types of vehicles. The problem resembles the Tactical FixedJob Scheduling Problem where ready times and deadlines of jobs are known in advance, andthe objective is to minimize the cost of machines to perform all the jobs. A job cannot beprocessed unless a machine is available at its ready time.The problem is formulated as an Integer Programming Model. A spread time constraintdetermines the regular time usage of the vehicles. The formulation is coded in LINGO 8.0 andGAMS 20.2 with CPLEX solver. Due to the complex nature of the problem, it is observedthat the optimal solution of even middle-size instances is very time consuming. Hence, wedevelop three different heuristic approaches for the problem, each one having two differenttypes based on overtime usage allowances. The algorithms are coded in C programmerLanguage using DEV C++ Compiler. The average behaviour of the algorithms is investigatedthrough computational experiments. Lower bound values for the problem are found usingGAMS developing some approaches, and the performances of the algorithms are comparedbased on these bounds. The problems whose number of trip is more than a hundred have beensolved in a very short time. The least solution of heuristic approaches is actually 10% greaterthan optimum solution.Key Words: Tactical Fixed Job Scheduling, Spread Time Constraints, Integer Programming,Heuristics.
Collections