GIS OSTRAVA 2008

VŠB - TU OSTRAVA, 27. - 30. 1. 2008

Abstract of paper No. 11
Title: SPOJENIE GIS PROSTRIEDKOV A METAHEURISTIK PRE RIEŠENIE OKRUŽNÝCH JÁZDY INTRAVILÁNE MIEST
APPLICATION OF GIS TOOLS AND METAHEURISTICS FOR THE SOLUTION OF STREET ROUTING PROBLEMS
Author(s): Matis, P.
Text:

Obsluha veľkého množstva zákazníkov v rámci intravilánu mesta je častou súčasťou mnohých logistických reťazcov. Kapacita obslužného vozidla je limitovaná a súčasne jedno vozidlo je schopné obslúžiť pomerne veľké množstvo zákazníkov. Úlohy takýchto vlastnosti sa často nazývajú aj úlohami okružných jázd v intraviláne mesta. Sú ukázané základné rozdiely medzi bežnými úlohami okružných jázd (Vehicle Routing Problem - VRP) a okružnými jazdami v intraviláne miest (Street Routing Problem - SRP). Hlavným problémom SRP je veľký počet zákazníkov a počet možných kombinácii ako ich utriediť do jednotlivých okružných jázd je nepredstaviteľný. Ako ukazujú experimenty na vzorke SRP expertné odhady priebehu okružných jázd sa môžu líšiť od optimálnych v rozmedzí 10% až 25%. V článku sú popísané efektívne spôsoby riadenia okružných jázd v intaviláne miest pomocou systémov na podporu rozhodovania okrem iného aj geografickými informačnými systémami. V článku sa okrem bežných kvantitatívnych mier vhodnosti riešenia používaných pri riešení všeobecných okružných jázd ako sú, celková dĺžka všetkých jázd alebo celkový čas trvania jednotlivých jázd, používajú ďalšie väčšinou kvalitatívne hodnotenia získaného riešenia. Všetky takéto kvalitatívne hodnotenia sú nazvané jedným termínom - vzhľadová atraktivita. Je prezentovaný vzťah medzi kvantitatívnymi a kvalitatívnymi mierami pri hľadaní vhodného riešenia, ktorý poskytuje nádej pre nájdenie takých riešení ktoré sú vhodné pre praktické použitie. Okrem iného sú prezentované porovnania niekoľkých známych úsporných heuristík na reálnych údajoch a tiež nová metaheuristika špecializovaná na tento typ problémov. Dôležitou vlastnosťou geografických informačných systémov pre použitie v riešení okružných jázd v intraviláne miest je interaktivita a užívateľsky priateľské prostredie a pritom otvorenosť celého systému. Softvér dokázže nájsť dobré riešenie, preskúmať veľkú množinu možností a odborník môže tieto zmeniť s možnosťou nájsť iné akceptovateľné riešenia. Je ukázaná aplikácia spojenia metaheuristiky s ArcView a ich použitie pre riešenie problémov adresnej pošty vo vybraných mestách Slovenskej republiky pre Slovenskú Poštu a.s. Spomenuté sú vlastnosti iných systémov pre podporu rozhodovania pre riešenie problémov okružných jázd ako sú TRANSCAD od firmy Caliper a GeoRoute vytvorený firmou GIRO pre Kanadskú poštu.

Servicing a large number of customers in a city zone is often a part of many logistics chains. The capacity of one delivery vehicle is limited, and at the same time, it usually serves a large number of customers. These problems are often called a Street Routing Problem (SRP). Key differences between Vehicle Routing Problems (VRP) and SRP are presented. The main problem of SRP is that the number of customers is large and the number of delivery path combinations is enormous As the experimental results show in the case of SRP, the error on the length of delivery routes based on an expert's judgment when compared to optimal solution is in the range of 10%-25%. As presented in the paper, the management of SRP could be effectively done only by using decision support systems such as Geographical Information Systems (GIS). Besides of classical measurements used in Vehicle Routing Problems as total length of routes or time required for delivery in each route other mostly qualitative measurements are presented. All these are named as visual attractiveness. In this paper it is presented possible relationship between quantitative and qualitative measurements that gives a promise for finding good solutions of SRP. Several saving based heuristics are evaluated on the real data and then compared to the new heuristic algorithm for solving SRP. One of the key properties of GIS for use with the routing software is the interactive and user-friendly environment that is flexible. Routing software can find a good solution and explore the possibilities and an expert can change calculated routes to explore other possibilities based on the expert's judgment. Paper presents practical use of new heuristics with the ArcView and solution of address mail for several cities in Slovakia served by Slovak Post a.s. Other Decision Support Systems that solve SRP are presented as TRANSCAD developed by Caliper corporation or GeoRoute developed by Canadian Post and GIRO.


Return to List of papers