Arc routing (original) (raw)
Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. Arc routings problems are NP hard, as opposed to route inspection problems that can be s
| Property | Value |
|---|---|
| dbo:abstract | Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. Arc routings problems are NP hard, as opposed to route inspection problems that can be solved in polynomial-time. For a real-world example of arc routing problem solving, Cristina R. Delgado Serna & Joaquín Pacheco Bonrostro applied approximation algorithms to find the best school bus routes in the Spanish province of Burgos secondary school system. The researchers minimized the number of routes that took longer than 60 minutes to traverse first. They also minimized the duration of the longest route with a fixed maximum number of vehicles. There are generalizations of arc routing problems that introduce multiple mailmen, for example the k Chinese Postman Problem (KCPP). (en) |
| dbo:wikiPageExternalLink | http://www.gerad.ca/~alainh/Trends.pdf http://www.lancaster.ac.uk/lums/search/%3Fq=arc+routing+problems |
| dbo:wikiPageID | 14040362 (xsd:integer) |
| dbo:wikiPageLength | 39526 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124945282 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pregolya dbr:Province_of_Burgos dbr:Route_inspection_problem dbr:School_bus dbr:Branch_and_bound dbr:List_of_graph_theory_problems dbr:Cutting-plane_method dbr:Vehicle_routing_problem dbr:Dead_mileage dbr:Deicing dbr:Integer_programming dbr:Jan_Karel_Lenstra dbr:Convex_optimization dbr:Branch_and_cut dbr:NP-complete dbr:NP-hard dbr:Convex_hull dbr:Leonhard_Euler dbr:Chinese_Postman_Problem_Complexity_List dbr:Street_sweeper dbc:Routing_algorithms dbr:Travelling_salesman_problem dbr:Held–Karp_algorithm dbr:Alexander_Rinnooy_Kan dbr:Dynamic_programming dbr:Eulerian_path dbr:Snow_removal dbc:Travelling_salesman_problem dbr:Snow_plow_routing_problem dbr:Kaliningrad dbr:Lagrange_multiplier dbr:Heuristic_(computer_science) dbr:Waste_collection dbr:Königsberg dbr:Capacitated_arc_routing_problem dbr:Mail dbr:Mixed_Chinese_postman_problem dbr:Salt dbr:Winter_service_vehicle dbr:Seven_Bridges_of_Königsberg dbr:NP-hardness dbr:Polynomial-time dbr:Snowplough |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Routing_algorithms dbc:Travelling_salesman_problem |
| gold:hypernym | dbr:Process |
| rdf:type | yago:WikicatRoutingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Election yago:Rule105846932 |
| rdfs:comment | Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. Arc routings problems are NP hard, as opposed to route inspection problems that can be s (en) |
| rdfs:label | Arc routing (en) |
| owl:sameAs | freebase:Arc routing yago-res:Arc routing wikidata:Arc routing https://global.dbpedia.org/id/4S2Y2 |
| prov:wasDerivedFrom | wikipedia-en:Arc_routing?oldid=1124945282&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Arc_routing |
| is dbo:wikiPageRedirects of | dbr:Chinese_Postman_Problem_Complexity_List dbr:ArcRoutingProblem dbr:Arc_Routing dbr:Arc_Routing_Problem dbr:Arc_Routing_problem dbr:Arc_routing_Problem dbr:Arc_routing_problem dbr:Arcroutingproblem |
| is dbo:wikiPageWikiLink of | dbr:Arp dbr:Vehicle_routing_problem dbr:Chinese_postman_problem dbr:Chinese_Postman_Problem_Complexity_List dbr:Travelling_salesman_problem dbr:Snow_plow_routing_problem dbr:Variable_neighborhood_search dbr:ArcRoutingProblem dbr:Arc_Routing dbr:Arc_Routing_Problem dbr:Arc_Routing_problem dbr:Arc_routing_Problem dbr:Arc_routing_problem dbr:Arcroutingproblem |
| is foaf:primaryTopic of | wikipedia-en:Arc_routing |