Abstract

Due to the regulation and laws concerning the emission of greenhouse gasses, carriers are starting to use electric vehicles for last-mile deliveries. The limited battery capacities of these vehicles necessitate visits to recharging stations during delivery tours of industry-typical length, which have to be considered in the route planning to avoid inefficient vehicle routes with long detours. This thesis seeks to propose new heuristic solution methods for Electric Vehicle Routing Problem with Time Windows (E-VRPTW), which incorporates the possibility of recharging at any of the available charging stations to minimize the total travel distance based on the Clarke and Wright (CW) Saving Heuristic. The solution method focuses on the construction of routes according to waiting time of vehicles, determined priority of customers with regard to their earliest starting service time, customers’ demands and etc. Moreover, the recharging rate, vehicle freight capacity, battery capacity, time windows and recharging time are considered to make it close to real-life logistics problems. Numerical tests are performed on newly designed instances by Schneider and performances of proposed methods are discussed. Keywords: Vehicle Routing Problem, Clarke and Wright Saving Heuristic, Green Logistic, Electric Vehicles, Combinatorial Optimization ÖZ : Sera gazlarının salınımı ile ilgili kural ve yasalardan dolayı taşımacılar şehir içi taşımalarını elektrikle çalışan araçlarla yapmaya başlamışlardır. Bu araçların sınırlı olan batarya kapasiteleri, taşıma sırasında zorunlu olarak batarya dolum istasyonlarında şarj edilmeleri gereksinimini doğurmakta ve bu durum da uzun ve verimsiz rotaların önlenmesi için rota planlamasında gözönüne alınmalıdır. Bu tezin amacı, alınan toplam mesafeyi enküçüklemek amacıyla şarjın tüm dolum istasyonlarında mümkün olduğu ve Clarke & Wright tasarruf algoritmasını esas alan Electric Vehicle Routing Problem with Time Windows (E-VRPTW) problemine yeni bir sezgisel çözüm yöntemi önermektir. Önerilen çözüm yöntemi öncelikle araçların bekleme sürelerine, müşterilerin zaman önceliklerine, taleplerine vs. göre rotalar oluşturmaya odaklanmaktadır. Problemin lojistik olarak daha da gerçekçi olmasını sağlamak üzere araçların taşıma kapasiteleri, batarya kapasiteleri, zaman aralıkları, şarj zamanları ve hızları da gözönüne alınmıştır. Schneider’in değerleri üzerinden sayısal deneyler de yapılmış ve önerilen yöntemlerin performansları da tartışılmıştır. Anahtar Kelimeler: Araç rotalama sorunu, Clarke ve Wright tasarruf sezgiseli, yeşil lojistik, elektrikli araçlar, birleşi eniyilemesi Master of Science in Industrial Engineering. Thesis (M.S.)--Eastern Mediterranean University, Faculty of Engineering, Dept. of Industrial Engineering, 2014. Co-Supervisor: Assoc. Prof. Dr. Bülent Çatay, Supervisor: Assist. Prof. Dr. Gökhan İzbırak.

Abstract

There has been growing interest in air transportation community to develop a routing decision model based on probabilistic characterization of severe weather. In the probabilistic air traffic management (PATM), decisions are made based on the stochastic weather information in the expected total cost sense. Probabilistic approach aims to enhance routing flexibility and reduce the risks associated with uncertainty of the future weather. In this research, a geometric model is adopted to generate optimal route choice when the future weather is stochastic. The geometric recourse model (GRM) is a strategic PATM model that incorporates route hedging and en-route recourse options to respond to weather change. Hedged routes are routes other than the nominal or detour route, and aircraft is re-routed to fly direct to the destination, which is called recourse, when the weather restricted airspace become flyable. Aircraft takes either the first recourse or the second recourse: The first recourse occurs when weather clears before aircraft reaches it flying on the initial route. The second recourse occurs when the aircraft is at the weather region. There are two variations of GRM: Single Recourse Model (SRM) with first recourse only and Dual Recourse Model (DRM) with both the first and second recourse options. When the weather clearance time follows a uniform distribution, SRM becomes convex with optimal route being either the detour or a hedged route. The DRM has a special property when the maximum storm duration time is less than the flight time to the tip of the storm on the detour route: it is always optimal to take the nominal route. The performance study is conducted by measuring the cost saving from either SRM or DRM. The result shows that there are cases with substantial cost saving, reaching nearly 30% with DRM.The ground-airborne hybrid model is an extension of the GRM, where both ground holding as well as route hedging are considered. The optimal combination of ground delay and route choice is determined by weather characteristics as well as the ground-airborne cost ratio. The numerical analysis reveals that whenever ground delay is required, the optimal route choice is the nominal one, while a non-nominal route is optimal when the ground delay is zero. There exists a unique critical cost ratio associated with given weather condition, which determines whether ground holding is optimal or not.

Abstract

Text in English; Abstract: English and Turkish Includes bibliographical references (leaves 48-49) x, 50 leaves On a regular day, almost 200,000 cars use Fatih Sultan Mehmet Bridge of Istanbul to commute between European and Asian side of the Bosporus. This enormous volume causes the traffic congestion to become a problem not only endemic to the bridge, but also cascading some major arterial roads of the city. This study includes a simulation model to analyze the traffic congestion problem in Fatih Sultan Mehmet Bridge of Istanbul. The main focus of this research are to identify the bottlenecks of the system, to discover vehicle behaviors in these bottlenecks, and to create a simulation model to predict the level of congestion on the bridge that will occur with different arrival rates of the vehicles. Our simulation analysis shows that even though there is no significant difference between the number of cars arriving to the bridge from both directions in the evening rush hour, when both directions on the bridge have four lanes (without any counter-flow lane), east direction (Europe-to-Asia) suffers more from traffic congestion due to lane merging taking place after the electronic toll collection (ETC) plazas. The analysis also suggests that a counter-flow lane in favor of the east (Europe-to-Asia) direction significantly improves the average number of cars congested at the entrance of the bridge. Ortalama bir günde İstanbul Boğazının Avrupa ve Asya yakası arasında seyahat etmek için neredeyse 200,000 araç Fatih Sultan Mehmet Köprüsünü kullanmaktadır. Bu miktarda araç sadece köprüde değil köprüye ulaşan ana arterlerde de trafik sıkışıklığı problemi oluşmasına neden olmaktadır. Bu çalışma Fatih Sultan Mehmet Köprüsündeki trafik sıkışıklığı probleminin analizi için oluşturulmuş bir simülasyon modelini içermektedir. Bu araştırmanın asıl odak noktası sistemin sahip olduğu darboğazların tespit edilmesi, araçların bu darboğazlardaki davranış biçimlerinin incelenmesi ve değişik araç geliş sıklıkları için trafik sıkışıklığı seviyesi tahmini yapılabilmesi için bir simülasyon modeli oluşturulmasıdır. Yapmış olduğumuz analizin önemli sonuçlarından bir tanesi köprünün her iki yakasına gelen araç sayısında önemli bir farklılık olamamasına rağmen akşam yoğunluğu saatlerinde her iki yöne 4 şerit ayrıldığında (ek şerit uygulaması olmadan) Doğu (Avrupa-Asya) yönüne giden araçlar trafik yoğunluğundan daha fazla etkilenmektedir. Bu yoğunluk farkı gişeler bölgesi sonrasındaki şerit birleşimi etkisinden kaynaklanmaktadır. Analizimizin önerisi Doğu yönüne (Avrupa-Asya) bir ek şerit verilerek köprü girişinde ortalama bekleyen araç sayısının azaltılması yönündedir.