Related Research Articles
The travelling salesman problem asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.
In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph. When the graph has an Eulerian circuit, that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time.
Parking is the act of stopping and disengaging a vehicle and leaving it unoccupied. Parking on one or both sides of a road is often permitted, though sometimes with restrictions. Some buildings have parking facilities for use of the buildings' users. Countries and local governments have rules for design and use of parking spaces.
A snowplow is a device intended for mounting on a vehicle, used for removing snow and ice from outdoor surfaces, typically those serving transportation purposes. Although this term is often used to refer to vehicles mounting such devices, more accurately they are known as winter service vehicles, especially in areas that regularly receive large amounts of snow every year, or in specific environments such as airfields. In other cases, pickup trucks and front end loaders are outfitted with attachments to fulfill this purpose. Some regions that do not frequently see snow may use graders to remove compacted snow and ice off the streets. Snowplows can also be mounted on rail cars or locomotives to clear railway tracks.
Snow removal or snow clearing is the job of removing snow after a snowfall to make travel easier and safer. This is done by both individual households and by governments and institutions.
A transport network, or transportation network, is a network or graph in geographic space, describing an infrastructure that permits and constrains movement or flow. Examples include but are not limited to road networks, railways, air routes, pipelines, aqueducts, and power lines. The digital representation of these networks, and the methods for their analysis, is a core part of spatial analysis, geographic information systems, public utilities, and transport engineering. Network analysis is an application of the theories and algorithms of graph theory and is a form of proximity analysis.
A runaway truck ramp, runaway truck lane, escape lane, emergency escape ramp, or truck arrester bed is a traffic device that enables vehicles which are having braking problems to safely stop. It is typically a long, sand- or gravel-filled lane connected to a steep downhill grade section of a main road, and is designed to accommodate large trucks or buses. It allows a moving vehicle's kinetic energy to be dissipated gradually in a controlled and relatively harmless way, helping the operator stop it safely.
A snow emergency is the active response plan when a snow storm severely impacts a city, county or town in the United States or Canada. Schools, universities, government offices, airports and public buildings may close during a snow emergency to prevent injuries during attempted travel; parking restrictions also usually go into effect to allow snowplows to clear the roads and streets effectively. The precise meaning of "snow emergency" varies depending on the issuing municipality. Snow emergencies are a common occurrence during the winter snowfall season in the Northern United States. The general public is alerted to snow emergency status via local broadcast stations, reverse 911 calls, mass text messaging services, public address systems, or lighted signals.
A winter service vehicle (WSV), or snow removal vehicle, is a vehicle specially designed or adapted to clear thoroughfares of ice and snow. Winter service vehicles are usually based on a dump truck chassis, with adaptations allowing them to carry specially designed snow removal equipment. Many authorities also use smaller vehicles on sidewalks, footpaths, and cycleways. Road maintenance agencies and contractors in temperate or polar areas often own several winter service vehicles, using them to keep the roads clear of snow and ice and safe for driving during winter. Airports use winter service vehicles to keep both aircraft surfaces, and runways and taxiways free of snow and ice, which, besides endangering aircraft takeoff and landing, can interfere with the aerodynamics of the craft.
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.
In public transportation, schedule adherence or on-time performance refers to the level of success of the service remaining on the published schedule. On time performance, sometimes referred to as on time running, is normally expressed as a percentage, with a higher percentage meaning more vehicles are on time. The level of on time performance for many transport systems is a very important measure of the effectiveness of the system.
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.
The Wyoming Department of Transportation (WYDOT) is a government agency charged with overseeing transportation infrastructure for the U.S. state of Wyoming. WYDOT's stated mission is “to provide a safe, high quality, and efficient transportation system.”
In graph theory and combinatorial optimization, a closure of a directed graph is a set of vertices C, such that no edges leave C. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem. It may be used to model various application problems of choosing an optimal subset of tasks to perform, with dependencies between pairs of tasks, one example being in open pit mining.
Hard infrastructure, also known as tangible or built infrastructure, is the physical infrastructure of roads, bridges, tunnels, railways, ports, and harbors, among others, as opposed to the soft infrastructure or "intangible infrastructure of human capital in the form of education, research, health and social services and "institutional infrastructure" in the form of legal, economic and social systems. This article delineates both the capital goods, or fixed assets, and the control systems, software required to operate, manage and monitor the systems, as well as any accessory buildings, plants, or vehicles that are an essential part of the system. Also included are fleets of vehicles operating according to schedules such as public transit buses and garbage collection, as well as basic energy or communications facilities that are not usually part of a physical network, such as oil refineries, radio, and television broadcasting facilities.
Meigu Guan is a Chinese mathematician and one of the country's leading experts on mathematical programming. He is known for his research on the route inspection problem, and served as president of Shandong Normal University.
In spatial analysis and geographic information systems, cost distance analysis or cost path analysis is a method for determining one or more optimal routes of travel through unconstrained (two-dimensional) space. The optimal solution is that which minimizes the total cost of the route, based on a field of cost density that varies over space due to local factors. It is thus based on the fundamental geographic principle of Friction of distance. It is an optimization problem with multiple deterministic algorithm solutions, implemented in most GIS software.
Each winter, the Canadian city of Montreal clears snow off of roads, sidewalks, and other public throughfares to make it easier and safer to travel. Montreal is the snowiest major city in North America and its snow removal operation is among the largest in the world, costing C$179.7 million in 2020. Montreal sees about 210 cm (82.5 in) of snowfall annually, with at least a centimetre of snow on the ground for nearly four months out of the year.
The mixed Chinese postman problem is the search for the shortest traversal of a graph with a set of vertices V, a set of undirected edges E with positive rational weights, and a set of directed arcs A with positive rational weights that covers each edge or arc at least once at minimal cost. The problem has been proven to be NP-complete by Papadimitriou. The mixed Chinese postman problem often arises in arc routing problems such as snow ploughing, where some streets are too narrow to traverse in both directions while other streets are bidirectional and can be plowed in both directions. It is easy to check if a mixed graph has a postman tour of any size by verifying if the graph is strongly connected. The problem is NP hard if we restrict the postman tour to traverse each arc exactly once or if we restrict it to traverse each edge exactly once, as proved by Zaragoza Martinez.
In mathematics, the capacitated arc routing problem (CARP) is that of finding the shortest tour with a minimum graph/travel distance of a mixed graph with undirected edges and directed arcs given capacity constraints for objects that move along the graph that represent snow plowers, street sweeping machines, or winter gritters, or other real-world objects with capacity constraints. The constraint can be imposed for the length of time the vehicle is away from the central depot, or a total distance traveled, or a combination of the two with different weighting factors.
References
- 1 2 Omer, Masoud (2007). "Efficient routing of snow routing of snow removal vehicles vehicles".
- ↑ Dussault, Benjamin; Golden, Bruce; Wasil, Edward (October 2014). "The downhill plow problem with multiple plows". Journal of the Operational Research Society. 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 0160-5682. S2CID 36977043.
- ↑ Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2.
- ↑ Bodin, Lawrence; Golden, Bruce (Summer 1981). "Classification in vehicle routing and scheduling". Networks. 11 (2): 97–108. doi:10.1002/net.3230110204.