DOĞRUSAL PROGRAMLAMA İLE ARAÇ ATAMA PROBLEMİNİN ÇÖZÜMLENMESİ

Abstract

Araç atama problemi, bir merkezi depoda yerleşmiş bulunan ve her biri aynı veya farklı kapasitelere sahip olan araçlar filosunun, her biri farklı bir yerleşime ve bilinen talebe sahip olan bir müşteriler kümesine toplam seyahat mesafesini veya süresini en küçükleyecek şekilde hizmet sunarak depoya geri dönmesi için gerekli rotaların belirlenmesi problemidir.

Çalışmanın temel unsurları, ulaşım sisteminin incelenmesi ve durak yerleri, güzergâhlar ve her güzergâhta kullanılacak taşıt cinsi hakkında en iyi çözümün bulunmasıdır. Çalışma da bir özel personel servis araçları firmasının toplam bir kamu kurumunda görev yapan personel için Ankara içindeki 5 ayrı güzergah içinde 25 durağa hizmet verisiyle ilgili problem formüle edilmiştir. Personel daha az yakıt tüketimiyle daha kısa bir zamanda taşınabilmektedir. Mevcut uygulamada kat edilen mesafe günlük 350 km iken 282 km’ye düşmüştür. Bu düşmeye rağmen sevk edilen araçların miktarını artmış, kaynakların etkin kullanılması ve gider konusunda tasarruf sağlanmıştır. Çalışma sonucunda, 10 adet durak tespit edilmiş ve önerilen çözümle % 10,42 oranında (yıllık 13.634,28 ₺) bir maliyet azaltımı olmuştur. Yıllık gider 825.415,8 ₺ iken 817.965,72 ₺ olarak gerçekleşmiştir. Yıllık kâr 13.634,28 ₺ yükselmiştir. Çalışmanın sonucunda hedeflenen hizmeti veren, hizmetin kalitesini ve personel memnuniyetini sağlayan en az maliyetli çözüm bulunmaya çalışılmış, Ankara’daki bir taşımacılık firmasında uygulama yapılmıştır.

Keywords

• Araç Atama Problemi,Doğrusal Programlama,Ulaştırma Modeli,Atama Modeli

AN ANALYSIS OF VEHICLE APPOINTMENT PROBLEM THROUGH LINEAR PROGRAMMING

Abstract

Vehicle appointment problem is the problem of determining the necessary routes for fleet vehicles of the same or different capacities and kept in a central car depot in order for them to return to the depot in such a way to minimize the total travel distance and travel time after having served a set of customers, each of whom are from a different location and have a notified demand. The basic aims of the study were analyzing the transportation system and stopping places, and sorting out the best solutions about the routes and the kind of vehicles to be used in each route.

In the study, the problem related to a private personnel vehicles company’s providing service for 25 stops in five different routes in Ankara for the personnel working in a public institution was formulated. The personnel can be transported in a shorter time and with less fuel consumption. In the current practice, the daily travelled distance decreased from 350 km to 282 km. In spite of this decrease, the number of dispatched vehicles increased and the efficient use of resources and costs have been economized. As a result of the study, 10 stops were identified and with the suggested solution a 10,42% cost reduction (annual 13.634,28 ₺) was achieved. The annual cost of 825.415,8 ₺ was reduced to 817.965,72 ₺. The annual profit increased to be 13.634,28 ₺. The study aimed at finding the most cost-efficient solution which would ensure the target service, service quality, and personnel satisfaction. The study was implemented in a transportation company in Ankara.

Keywords

• Vehicle Assisgnment Problem,Linear Programming,Transportation Model,Assingment Model

References

1. Ai, J., Kachitvichyanukul, V. (2009). A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers & Operations Research, 36: 5, 1693 -1702.
2. Bektaş, T. ve S. Elmastaş (2004). Okul Araç Rotalama Probleminin Tamsayılı Programlama ile Çözümü”, 24. Yöneylem Araştırması /Endüstri Mühendisliği Ulusal Kongresi YA/EM’2004’nde Sunulan Bildiri, 15 -18 Haziran, Gaziantep– Adana, 3.
3. Bowerman, R., B. Hall ve P. Calamai, (1995a). A Multiobjective Optimization Approach to Urban School Bus Routing: Formulation and Solution Method, University of Waterloo, Waterloo, ON, Canada, 13.
4. Braca, J., J. Bramel, B. Posner, ve D. Simchi-Levi (1997). A Computerized Approach to the New York City School Bus Routing Problem” IIE Transactions, Cilt No 29, Sayı 8, 693 -702.
5. Bodin, L. ve L. Berman (1979). Routing and Scheduling of School Busses by Computer, “Transportation Science” Cilt No 13, Sayı 2, 113 -129.
6. Chapleau, L., Ferland, J., Rousseau, J. (1985). Clustering for Routing in Densely Populated Areas. European Journal of Operational Research, 20: 48 -57.
7. Dantzig G.B., Ramser J. H. (1959). The Truck Dispatching Problem, Management Science, 6.
8. Demiral, M. F. (2008). Servis Araçlarının Rotalanmasında Optimizasyon ve Bir Uygulama, Y. Lisans Tezi, Süleyman Demirel Üniversitesi, Sosyal Bilimler Enstitüsü İşletme Anabilim Dalı, Yüksek Lisans Tezi, Isparta, 2.

9. Dulac, G., Ferland, J., Fogues, P. A. (1980). School Bus Routes Generator in Urban Surroundings. Computers and Operations Research, 7:199 -213.
10. Laporte, G., Nobert, S. Y., Taillefer (1987). Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems, Transportation Science, Cilt No 22, Sayı 3, 161.
11. Lee, S. ve L. Moore (1977). Multi-Criteria School Bussing Models, Management Science, Cilt No 23, Sayı 7, 705.
12. Li, L. ve Fu, Z., (2002). The School Bus Routing Problem: A Case Study. Journal of Operations Resource Society, 53: 552 -558.
13. Montané, T, F, A., Galvão, R, D. (2006). A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service. Computers and Operations Research 33: 3, 595 –619.
14. Spada, M., M. Bierlaire, TH. M. Liebling (2005). Decision-Aiding Methodology for the School Bus Routing and Scheduling Problem”, Tranportation Science, Cilt No 39, Sayı 4, 477 -490.
15. Swersey, A. J. ve W. Ballard (1984). Scheduling School Buses”, Management Science, Cilt No 30, Sayı 7, 844 -853.
16. Timor, M. (2001). Yöneylem Araştırması ve İsletmecilik Uygulamaları, İstanbul: İstanbul Üniversitesi Basımevi Müdürlüğü, 128.
17. Toth, P., Vigo, D., (2002), The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia.
18. Winston, W. L. (1994). Operations Research: Applications and Algorithms, Duxbury Press, California.