Route Optimization কী? Algorithm, Constraint এবং API

Route optimization হলো stop ordering এবং vehicle assign করার অনুশীলন যাতে একটি fleet সবচেয়ে কম time, distance বা cost-এ তার কাজ শেষ করে। এটি একজন delivery driver যে বিকেল ৪টায় শেষ করে এবং একই van ও একই stop সহ যে বিকেল ৭টায় শেষ করে এর মধ্যে পার্থক্য। একটি logistics app-এ প্রতিটি "optimised route" button-এর নিচে একটি solver বসে যা সবেমাত্র millions of সম্ভাব্য ordering-এর মধ্য দিয়ে চিবিয়েছে এবং একটি বেছে নিয়েছে।

এই guide ব্যাখ্যা করে route optimization আসলে কী, solver কীভাবে এটির কাছে আসে, কোথায় এটি বাস্তব জগতে দেখা যায় এবং কোন constraint ও সমস্যাগুলি একটি demo-কে production থেকে আলাদা করে।

Route Optimization আসলে কী

Computer science-এ, route optimization দুটি classic problem-এর মধ্যে থাকে। Travelling Salesman Problem (TSP) প্রশ্ন করে: শহর-এর একটি list এবং তাদের মধ্যে দূরত্ব দেওয়া হলে, প্রতিটি শহর ঠিক একবার visit করে এবং start-এ ফিরে আসে এমন সবচেয়ে ছোট route কী? এটি একটি single-vehicle problem। Vehicle Routing Problem (VRP) এটিকে একটি fleet-এ সাধারণীকরণ করে: একটি depot, একগুচ্ছ customer এবং কয়েকটি vehicle দেওয়া হলে, customer-দের কীভাবে vehicle-এর মধ্যে ভাগ করা উচিত এবং প্রতিটি vehicle তাদের কোন order-এ visit করা উচিত?

উভয় problem NP-hard। সম্ভাব্য ordering-এর সংখ্যা stop-এর সংখ্যার সাথে factorially বৃদ্ধি পায়। বিশটি stop ইতিমধ্যে 10-এর 18 power-এর বেশি সম্ভাব্য route তৈরি করে। কোনো exact algorithm সেই space real time-এ search করতে পারে না। Production-এ Optimization তাই perfect answer খুঁজে পাওয়ার বিষয় নয়। এটি কাজ করার মতো দ্রুত একটি খুব ভাল answer খুঁজে পাওয়ার বিষয়।

Solver কীভাবে Problem-এর কাছে আসে

কারণ search space বিশাল, real solver বেশ কয়েকটি technique blend করে।

ছোট সমস্যার জন্য (প্রায় ১৫টি stop-এর কম), branch-and-bound বা integer programming-এর মতো exact method কয়েক সেকেন্ডে একটি provably optimal solution return করতে পারে। সেই scale-এর বাইরে, exact method practical থাকে না এবং field heuristic-এ চলে যায়।

একটি typical pipeline একটি initial route তৈরি করতে nearest-neighbour বা Clarke-Wright savings algorithm-এর মতো একটি constructive heuristic দিয়ে শুরু হয়। সেই route তারপর একটি metaheuristic-এর কাছে hand করা হয়, যা iteratively stop swap করে, sub-tour reverse করে বা vehicle-এর মধ্যে stop সরিয়ে objective উন্নত করে। Simulated annealing, tabu search, large neighbourhood search এবং genetic algorithm সবচেয়ে সাধারণ পছন্দ। প্রতিটির একই আকৃতি: একটি change চেষ্টা করুন, এটি গ্রহণ করবেন কিনা সিদ্ধান্ত নিন, একটি fixed time budget-এর জন্য পুনরাবৃত্তি করুন।

অন্য critical input হলো distance matrix: প্রতিটি pair of stop-এর মধ্যে travel time ও distance-এর একটি precomputed table। Optimizer তার search-এর সময় matrix-কে millions বার query করে, তাই matrix একটি routing engine দ্বারা একবার সামনে তৈরি হয় এবং solver চলাকালীন memory-তে রাখা হয়।

Route Optimization কোথায় দেখা যায়

Route optimization নীরবে operational business-এর একটি দীর্ঘ list চালায়।

• Last-mile delivery: parcel carrier, grocery delivery এবং e-commerce fulfilment সবই দিনে প্রতি van-এ কয়েক ডজন থেকে শত stop sequence করে
• Field service: HVAC technician, telecom installer এবং home health worker appointment window ও skill requirement সহ একটি region জুড়ে customer visit করে
• Mobile workforce: utility crew, meter reader এবং inspector mixed task type সহ territory cover করছে
• Food delivery: restaurant aggregator একটি single rider trip-এ একাধিক order batch করছে যখন geography মিলে যায়
• Waste collection: municipal truck fixed weekly round চালাচ্ছে যেখানে ছোট reordering real fuel সাশ্রয় করে
• Sales rep: territory planning যেখানে একজন rep দিনে ৮ থেকে ১২টি account visit করে এবং order drive time ও meeting density-এর জন্য গুরুত্বপূর্ণ

প্রতিটি ক্ষেত্রে user সঠিক order-এ stop-এর একটি list দেখে। কাজটি এর পেছনে optimizer-এ ঘটে।

যে Constraint গুরুত্বপূর্ণ

একটি solver যা শুধুমাত্র distance minimise করে তা একটি toy। Production routing তার constraint দ্বারা সংজ্ঞায়িত।

• Vehicle capacity: প্রতিটি van-এর একটি weight, volume বা pallet limit আছে যা assign করা stop অতিক্রম করা উচিত নয়
• Time window: customer ৯ থেকে ১১টার মধ্যে delivery আশা করে এবং ১১:০৫-এ পৌঁছানো একটি ব্যর্থতা
• Driver shift: সর্বাধিক working hour, mandatory break এবং নির্দিষ্ট depot-এ start ও end
• Skill বা vehicle matching: একটি fridge install-এর জন্য একটি দুজনের team দরকার, একটি cold-chain delivery-এর জন্য একটি refrigerated van দরকার
• Multi-depot: বড় fleet বেশ কয়েকটি warehouse থেকে dispatch হয় এবং solver সিদ্ধান্ত নেয় কোন depot কোন stop handle করে
• Return-to-base: কিছু route open (driver বাড়িতে শেষ করে), অন্যগুলি closed (driver depot-এ ফিরে যায়)

প্রতিটি constraint route-এর feasible set-কে সংকুচিত করে এবং solver-কে এমন solution-এর দিকে ঠেলে দেয় যা কাগজে কিছুটা খারাপ দেখায় কিন্তু আসলে deliverable।

Production-এ সমস্যা

Route optimization এমন একটি category যেখানে demo সর্বদা কাজ করে এবং rollout প্রায়ই করে না।

ভুল objective optimise করা. Distance minimise করা default, কিন্তু অনেক fleet-এর জন্য revenue বা service-level compliance kilometre সাশ্রয়ের চেয়ে বেশি গুরুত্বপূর্ণ। ২ কিমি-এর খরচে একটি অতিরিক্ত parcel drop করা একটি route সাধারণত একটি জয়।

Free-flow বনাম traffic-aware time. Raw road speed থেকে তৈরি একটি matrix আপনাকে বলবে একটি route ৪ ঘন্টা নেয় যখন rush-hour traffic-এ এটি ৬ নেয়। Route যে time of day-এ চলবে তার জন্য traffic-aware travel time expose করে এমন একটি routing engine ব্যবহার করুন।

No real-time replanning. Plan সেই মুহুর্তে drift হয় যখন একজন driver অপ্রত্যাশিত traffic-এ পড়ে, একজন customer cancel করে বা একটি নতুন stop আসে। Operations team-এর সকালের কাজ ফেলে না দিয়ে mid-day-তে অবশিষ্ট stop re-optimise করার একটি উপায় প্রয়োজন।

Frozen plan staleness. একটি weekly fixed route জানুয়ারিতে optimal দেখাত এবং এখন ২০ percent খারাপ কারণ customer সরে গেছে, volume পরিবর্তিত হয়েছে এবং একটি one-way street উপস্থিত হয়েছে। Optimization periodically re-run করুন এবং driver-দের উপর change জোর করার আগে নতুন plan-কে live-এর সাথে তুলনা করুন।

MapAtlas-এ Route Optimization

MapAtlas Optimize Route API এমন constraint সহ single-vehicle এবং fleet routing problem solve করে যা operations team-এর আসলে প্রয়োজন: capacity, time window, shift, skill এবং multi-depot setup। এটি প্রতি vehicle-এ একটি sequenced plan return করে যার সাথে প্রতিটি stop-এর জন্য predicted arrival ও departure time থাকে।

এটি স্বাভাবিকভাবে MapAtlas stack-এর অন্য দুটি endpoint-এর সাথে pair হয়। Distance Matrix API traffic-aware time সহ travel-time table তৈরি করে যা solver consume করে, যাতে rush hour-এ plan টিকে থাকে। Directions API order fix হওয়ার পরে consecutive stop-এর মধ্যে actual turn-by-turn road path আঁকে, যাতে একটি driver app একটি সরলরেখার পরিবর্তে একটি real polyline দেখাতে পারে।

Route optimization একটি slide deck-এ glamorous দেখাবে না। এটি একটি solver, একটি matrix এবং একটি constraint list। কিন্তু এটিই সেই layer যা সিদ্ধান্ত নেয় একটি fleet সময়মতো এবং budget-এর মধ্যে তার দিন শেষ করে কিনা, এবং এটি সঠিকভাবে পাওয়াই সেই routing feature-কে আলাদা করে যা ship হয় এবং যেটি নীরবে বন্ধ করে দেওয়া হয়।