پديد آورندگان :
هاشمي، وحيد دانشگاه صنعتي خواجه نصيرالدين طوسي - دانشكده مهندسي نقشه برداري , سعدي مسگري، محمد دانشگاه صنعتي خواجه نصيرالدين طوسي - دانشكده مهندسي نقشه برداري , محمدي كزج، پويا دانشگاه صنعتي خواجه نصيرالدين طوسي - دانشكده مهندسي نقشه برداري
كليدواژه :
اشتراك سواري , الگوريتم ژنتيك ارتقا يافته , عملگرهاي جهش ابتكاري , الگوريتم هاي جست و جوي محلي
چكيده فارسي :
افزايش بي‌رويه تعداد وسايل نقليه در شهرها منجر به مشكلات متعددي ازجمله آلودگي هوا، آلودگي صوتي و مشكلات ترافيكي مي‌شود. جهت غلبه بر اين مشكلات نيازمند به‌كارگيري روش‌هاي نوين در بحث مديريت شهري مانند به‌كارگيري سامانه‌هاي حمل‌ونقل نوين همچون سيستم اشتراك سواري هستيم. هدف از اين مطالعه ايجاد و پياده‌سازي مدلي مناسب، براي اشتراك سواري با به‌كارگيري خودروهايي با ظرفيت مختلف و با استفاده از الگوريتم ژنتيك ارتقا يافته است تا بتوان از طريق گروه‌بندي مسافراني كه به لحاظ پارامترهاي مكاني-زماني سفر شباهت دارند، صندلي‌هاي خالي وسايل نقليه و به‌تبع آن تعداد وسايل عبوري در سطح شهر را كاهش داد. از طرفي مسيري بهينه براي هر گروه از مسافران برنامه‌ريزي نمود به‌نحوي‌كه مسافت سفر هر گروه و به‌تبع ميزان معطلي در طول سفر براي هر يك از مسافران و رانندگان نيز كمينه شود. ازاين‌رو در اين الگوريتم چهار تابع هدف، كمينه‌سازي مسافت پيموده شده مجموع سفرها، مجموع زمان معطلي (انحراف از زمان‌هاي ايده آل) در مبدأ و مقصد مسافران، تعداد وسايل نقليه استفاده‌شده و تعداد صندلي‌هاي خالي در نظر گرفته‌شده‌اند. در اين تحقيق از دو عملگر جهش ابتكاري و دو الگوريتم جست‌وجوي محلي تحت عناوين الگوريتم مبتني بر ژنتيك و الگوريتم ابتكاري مبتني بر اولويت زمان سفر مسافران به‌منظور ارتقا الگوريتم ژنتيك براي اين حالت خاص استفاده‌شده است. سپس الگوريتم ارتقا يافته جهت حل مسئله اشتراك سواري روي يك شبكه فرضي با تعداد 46 گره پياده‌سازي شده است. درنهايت حالات مختلف الگوريتم و استفاده از عملگرهاي توسعه‌يافته طي سناريوهايي مختلف تست، ارزيابي و مقايسه شدند.
چكيده لاتين :
An increase in the number of vehicles in cities leads to several problems, including air pollution, noise pollution, and congestion. To overcome these problems, we need to use new urban management methods, such as using intelligent transportation systems like ride-sharing systems. The purpose of this study is to create and implement an improved genetic algorithms model for ride-sharing with non-homogeneous vehicles (like taxis and vans with a capacity of 4 and 10 passengers). The proposed genetic algorithm can group passengers according to their trip similarity based on Spatio-temporal parameters to reduce the number of empty seats in vehicles, followed by the number of vehicles through the city, and get the optimal traveling path for each group of passengers.
Optimal traveling path planning should also be considered to minimize each group's travel distance and, as a result, the time delays during the trip for each passenger and driver. Therefore, in this algorithm, four objective functions are considered. The objectives include minimizing the total travel distance of trips, the entire time delay (deviation from ideal times) at the origin and destination of passengers, number of vehicles, and number of empty seats.
Due to the previous studies and the lack of combination of these objective functions mentioned above, in this article, complete research was conducted to create a model by combining these objective functions. Combining these objective functions complicates the model and, consequently, presents challenges in its implementation. To overcome these problems, Two innovative mutation operators and two local search algorithms under the titles of genetic algorithm and innovative algorithm based on passengers' travel time priority proposed to improve the genetic algorithm's exploitation ability and to reach the global optimum answer.
The first innovative mutation operator is called join-vehicles. This innovative operator aimed to reduce the number of used vehicles by using vehicles' maximum capacity to serve passengers. As discussed in this paper, conventional mutation operators such as insert or scramble operators do not have adequate ability to solve this problem. In this innovative method, the indices of two genes related to two random vehicles' positions in the entered chromosome are chosen randomly. The goal is to remove the second vehicle and combine its passengers with the first vehicle to travel beside its passengers. Also, the arrangement of boarding and disembarking this set of passengers is planned in a way that the car's capacity condition is always satisfied; therefore, there will no longer be a restriction on passengers' combination in a van with a taxi vice versa.
The second innovative mutation operator was proposed to change the van into a taxi. During the training, we would observe that some vans were used to serve the passengers while less than half of their capacity was occupied. At first, this operator replaces the van vehicles on the input chromosome with random taxis not used on the chromosome and recalculates this chromosome's cost with the new state. If this new state reduces the chromosome's cost, the taxi will be replaced with that van in the chromosome.
Another issue that arises after applying the mentioned mutation operators on the chromosome is how to take turns for passengers to board and disembark in altered parts of the chromosome to respond to requests optimally. Therefore, two local search algorithms based on the innovative passengers' time priority to board and disembark and the traditional genetic algorithm have been implemented to increase the solution quality. These two algorithms are applied to the altered part(s) of the input chromosome and replace the resulting output with this/these part(s).
About the innovative local search algorithm based on the time priority of boarding and disembarking passengers, a passenger whose expected time to board is earlier than the other passengers of a group gets on the vehicle first. This passenger's expected time to get off at his destination is compared with the other passengers' expected time to board if he/she has higher priority than the others. Then the vehicle reaches him/her to his/her destination first. Then the vehicle goes to the origin of the next passenger, who has more priority to get in the vehicle. According to passengers' expected time priority, this procedure is repeated to board and disembark them properly.
In this model, 18 travel requests, including 26 passengers (some travel requests included more than one passenger), were considered, which want to be transferred in a hypothetical road network that contains 46 nodes and 75 edges. Finally, the implemented model was tested and evaluated during six different scenarios. The results indicate the efficiency of the implemented model of this paper. It should be noted that according to the chromosome encoding method used in this paper, which is similar to some previous studies, the model of this paper can be used, tested, and evaluated in other areas related to the vehicle routing problem.
