In the modern era, transportation is a part of human life. For now, people use public and private transport services to get to schools, offices, or just hang out… Demand Responsive Transport systems serve elders or disabled passengers in rural areas by scheduling small or medium vehicles on flexible routes. Trucks transport goods from stores to suppliers or users. Some logistic companies like FedEx can carry freights overseas, etc.
Report of Bureau of Transportation Statistics – U.S. Department of Transportation shows that $9000 average expenditures for each household per year. In 2011, the freight transportation system served 7.4 million business establishments, 118.7 million households, and more than 89,000 government units. In 2012 the Nation’s freight system moved 53.9 million tons of goods worth $47.5 billion each day. They also report 1.8 billion annual metric tons of carbon dioxide emissions. A considerable research effort has been carried out by scientists of Operations Research community that optimize the transportation planning in order to save operational cost and reduce negative social impacts such as traffic jam and pollution. The research focuses on both transportation models and optimizing routing solutions to serve passengers and freights. Vehicle routing problem (VRP) is one of the earliest routing problems, which aims to optimize the delivery of goods from a distribution centre, and was described by Dantzig et al. in 1959 [1]. Figure 1 illustrates the route planning problem in which a set of identical trucks with limited capacities are scheduled to deliver goods to customers so that it satisfies the demands of customers and minimizes the total transportation cost.
Figure 1. Illustration of Vehicle Routing
Recently, a hybrid transportation model has been proposed that combines trucks and unmanned aerial vehicles (UAV) to deliver goods to customers. Murray and Chu introduced this model in 2015 [2]. Figure 2 illustrates this scenario in which a truck travels with a UAV. The truck can carry heavy freights on long-distance trips while the UAV with limited batteries can only carry light freights on short-distance trips but it can fly very fast compared to the truck.
Figure 2. Illustration of delivering freights using both trucks and UAV
Demand responsive transport is a kind of public transport that schedules flexibly medium vehicles (e.g., minibuses) for serving people requests. In this scenario, passengers are required to make reservation (i.e., pickup and delivery locations, preferred pickup time, etc.) in advance. The operation centre will schedule (with help of optimization software tools) the vehicles to serve passengers request in such a way that the waiting times of passengers are minimal, the occupancy of vehicles are maximized, and the total traveling cost of vehicles is reduced. For passengers, this transportation model is more confortable than public buses and less expensive than traditional taxis. In 2014, Li et al. proposed a transportation model that combines the services of passengers and freights in share-a-ride taxis [3]. In this scenario, a passenger does not want to share a ride with other passengers but he is willing to share a ride with light parcels with a reduced fee. Figure 3 illustrates the people and parcels share-a-ride taxis. VIA [4] is an example of demand responsive transport with sharing options.
Figure 3. Illustration of share-a-ride taxis
Finding optimal routes for these transportation problems are computationally hard. Various algorithmic approaches have been proposed to solve these routing problems. These approaches are divided into two categories: exact and metaheuristic techniques. Exact techniques include Branch-and-Cut, Branch-and-Price, Constraint Programming, and aim at finding optimal solution to the given problem. However, these exact techniques can only be applied to small problem instances, as the time complexity is exponential of the size of the input. In contrast, metaheuristic techniques aim at finding near optimal solutions to large problem instances in reasonable time. Branch-and-cut technique relies on a mixed integer-programming (MIP) model. For VRP problems, the MIP model usually contains an exponential number of constraints. It uses a powerful linear programming solver to solve a relaxed problem (some constraints are relaxed), and then add dynamically relaxed constraints to cut out invalid solutions. Constraint Programming (CP) is another technique to solve combinatorial optimization problems optimally by exploring solutions space entirely. CP is a combination of propagation and branching procedures. The propagation aims at narrowing the solutions space by removing values from the domains of variables that do not appear in the optimal solutions. The branching partitions the original problem into smaller problems by splitting the domain or enumerating all values of a selected variable. To attack large-scale problems, neighbourhood search (e.g., Tabu Search, Simulated Annealing) is popular among metaheuristic techniques. In this approach, this search starts from an initial solution, which is generated randomly or by some greedy algorithms. After that, it iteratively moves from a current solution to one of its neighbours. A neighbour of a current solution is generated by applying a move operator which modifies locally the current solution. Figure 4 illustrates some of the move operators proposed in the literature for VRP problems.
Figure 4. Illustrating some move operators in neighborhood search for VRP problems
Large Neighbourhood Search (LNS) is a recent technique that uses CP solvers to select the most promos sing neighbour in large neighbourhood structures. In the VRP problems, LNS is realized by removing k customers and re-inserting them into other positions of the routes in an optimal way.
Optimization in transportation is still an active research topic. The research focuses on either proposing new dedicated algorithms that improves existing techniques for a specific problem, or developing a generic solver frameworks that allow users to model and solve flexibly different variants of transportation optimization problems as well as to adapt quickly existing model when additional constraints and objectives appear. Many big companies and transnational cooperation are developing and using optimization technology for transportation services such as: UPS, FedEx, IBM, SAP, Oracle, Google, etc…
References [1]. George Bernard Dantzig and John Hubert Ramser. The Truck Dispatching Problem. Management Science 6(1), pp 80-91, 1959. [2]. Murray, C.C., Chu, A.G.: The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies 54, pp 86–109 (2015) [3]. B. Li, D. Krushinsky, H. A. Reijers, T.V. Woensel, The Share-a-Ride Problem: People and parcels sharing taxis, European Journal of Operation Research, Vol. 328(1), 31-40 (2014) [4]. VIA. http://ridewithvia.com/
Pham Quang Dung – FPT Software  
Related posts: