वाहन की रूटिंग, ऑप्टिमाइज़ेशन के सबसे आम कामों में से एक है. इसके तहत, कई तरह की जगहों पर जाने वाले वाहनों के ग्रुप के लिए, सबसे अच्छा रास्ता ढूंढना होता है. आम तौर पर, "सबसे अच्छे" का मतलब सबसे कम कुल दूरी या लागत वाले रास्तों से है. यहां रूटिंग से जुड़ी समस्याओं के कुछ उदाहरण दिए गए हैं:
- पैकेज डिलीवरी करने वाली कोई कंपनी, डिलीवरी के लिए ड्राइवर के लिए रूट असाइन करना चाहती है.
- एक केबल टीवी कंपनी, टेक्नीशियन के लिए घर की सेवा कॉल करने के रास्ते तय करना चाहती है.
- राइड शेयर करने वाली एक कंपनी ड्राइवरों के लिए रूट असाइन करना चाहती है, ताकि वे यात्रियों को पिक अप और ड्रॉप कर सकें.
रास्ते की सबसे मशहूर समस्या, ट्रैवलिंग सेल्सपर्सन समस्या (टीएसपी) है: ऐसे सेल्समैन के लिए सबसे छोटा रास्ता पता करें जिसे अलग-अलग जगहों पर ग्राहकों के पास जाना होता है और शुरुआती पॉइंट पर लौटना होता है. टीएसपी को एक ग्राफ़ से दिखाया जा सकता है, जिसमें नोड जगहों से जुड़े होते हैं. साथ ही, किनारे (या चाप), जगहों के बीच की सीधी यात्रा को दिखाते हैं. उदाहरण के लिए, नीचे दिए गए ग्राफ़ में एक टीएसपी दिखाई गई है, जिसमें सिर्फ़ चार जगहें हैं, जिनके लेबल A, B, C, और D हैं. दो जगहों के बीच की दूरी, उन जगहों के किनारों के बगल में मौजूद संख्या से तय होती है.
सभी संभावित रास्तों की दूरी की गणना करके, आप देख सकते हैं कि सबसे छोटा रास्ता ACDBA है, जिसके लिए कुल दूरी 35 + 30 + 15 + 10 = 90 है.
ज़्यादा जगहें होने पर समस्या और मुश्किल हो जाती है. ऊपर दिए गए उदाहरण में, सिर्फ़ छह रूट दिए गए हैं. हालांकि, अगर 10 जगहों की जानकारी (शुरुआत की जगह को नहीं गिना जाता) है, तो रास्तों की संख्या 362880 होगी. वहीं 20 जगहों के लिए, यह संख्या सीधे 2432902008176640000 पर पहुंच जाती है. सभी संभावित रास्तों की पूरी खोज से सबसे छोटा रास्ता मिल जाएगा, लेकिन यह छोटी जगहों को छोड़कर सभी के लिए कंप्यूटेशनल तरीके से मुश्किल है. बड़ी समस्याओं के लिए, ऑप्टिमाइज़ेशन तकनीकों की ज़रूरत होती है, ताकि आसानी से सॉल्यूशन जगह को खोजा जा सके और सबसे अच्छा (या करीब-करीब सबसे अच्छा) समाधान ढूंढा जा सके.
टीएसपी का एक सामान्य वर्शन है, वाहन के रूट में समस्या (वीआरपी) जिसमें कई वाहन होते हैं. ज़्यादातर मामलों में, वीआरपी में सीमाएं तय होती हैं: उदाहरण के लिए, वाहनों में तय वज़न या मात्रा में सामान रखने की क्षमता हो सकती है. इसके अलावा, ग्राहकों के अनुरोध किए गए समय विंडो के दौरान ड्राइवर को कारोबार की जगहों पर जाना पड़ सकता है.
OR-टूल से कई तरह के वीआरपी हल किए जा सकते हैं. इनमें ये शामिल हैं:
- ट्रैवलिंग सेल्सपर्सन की समस्या, रूट बनाने से जुड़ी क्लासिक समस्या, जिसमें एक ही वाहन इस्तेमाल होता है.
- वाहन के रूट में होने वाली समस्या, एक से ज़्यादा वाहनों वाली टीएसपी की सामान्य जानकारी.
- कम क्षमता वाला वीआरपी, जिसमें वाहनों में सामान ले जाने की ज़्यादा से ज़्यादा क्षमता होती है.
- टाइम विंडो के साथ वीआरपी, जिसमें वाहनों को तय समय अंतराल पर जगहों पर जाना ज़रूरी है.
- संसाधनों के साथ वीआरपी, जैसे कि डिपो पर वाहनों को लोड और अनलोड करने के लिए खाली जगह या कोई व्यक्ति. यह रूट के लिए शुरुआती पॉइंट होता है.
- गतिविधियों में गिरावट के साथ वीआरपी, जहां वाहनों को सभी जगहों पर जाने की ज़रूरत नहीं होती. हालांकि, हर विज़िट पर आने पर आपको जुर्माना देना होता है.
वाहन की रूटिंग से जुड़ी समस्याओं को हल करने की सीमाएं
गाड़ियों के रूट की समस्याएं बड़ी हैं, जिन्हें हल करने में लगने वाला समय समस्या के आकार के साथ-साथ तेज़ी से बढ़ता है. काफ़ी बड़ी समस्याओं का सबसे सही हल निकालने में OR-टूल (या कोई भी दूसरे रूटिंग सॉफ़्टवेयर) साल लग सकते हैं. इस वजह से, OR-टूल कभी-कभी ऐसे समाधान दिखाता है जो अच्छे होते हैं, लेकिन बेहतर नहीं होते. बेहतर हल ढूंढने के लिए, सॉल्वर की खोज के विकल्प बदलें. उदाहरण के लिए, खोज की रणनीति बदलना देखें.