With the gift-giving season almost upon us and increasing concerns about the environmental effects of all those deliveries and pickups, it is timely that researchers should turn their attention to the so-called Traveling Salesman Problem. Writing in a forthcoming issue of the Inderscience publication the International Journal of Logistics Systems and Management, researchers suggest a new approach to cutting journey times of courier services everywhere.
According to Chandra Sunil Kumar and T.T. Narendran of the Department of Management Studies, at IIT-Madras, in Chennai, India, the Traveling Salesman Problem, or to give it its modern name the Vehicle Routing Problem (VRP), is one of the biggest headaches for companies running delivery and pickup services - how to ensure the route taken by the couriers is not only as short as possible and so uses the least fuel but also ensures that all drop-offs and pick-ups are made in a timely manner. The efficiency of services involving express couriers, dial-a-ride systems, and partial-truck-load carriers might all be improved.
Narendran and colleagues have devised a computer model to investigate how companies might map out the optimum routes for their couriers.
In their model the researchers consider a single vehicle operating within a region. Each day, there are calls from customers, packages to deliver, and others to collect and deliver elsewhere. Static customer requests are those that are known in advance, while dynamic requests arise as the day progresses. The vehicle starts from the depot, moves to serve static customers according to a schedule of advance requests. As the day progresses, new requests come in and the dispatcher has to re-route to fulfill these new requests while minimizing the total distance traveled in accommodating advance bookings.
The vehicle then follows the latest determined route until a new dynamic request arrives. At that time, the vehicle is between the start and finish of the original plan. Now the plan has to add a pickup and delivery point into the unexecuted part of the plan so that the additional distance to be traveled is minimized. At this juncture, the computer model inserts a heuristic - a rule of thumb. In one method, the customer's new request is positioned appropriately between two of the places to be visited as per the original plan. In the second approach, the entire sector remaining to be served is reframed with the inclusion of the new request; this part of the problem is solved afresh using an optimization approach.
The team has carried out tests of the model computationally and found that the distance traveled by the vehicle increases with increasing numbers of new requests. However, the heuristics can work in real-time and every time a new request arises, they can process the information and re-route the vehicle to keep the total distance as low as possible.
The team points out that their system will not only help courier companies but could be used equally well by dial-a-ride services, which fill the gap between public transport and taxi cabs, fast food and groceries home deliveries, emergency service responses, including fire, police, and ambulance, repair services, and perhaps even parcel and mail delivery services.
T.T. Narendran | EurekAlert!
Tool helps cities to plan electric bus routes, and calculate the benefits
09.01.2017 | International Institute for Applied Systems Analysis (IIASA)
Realistic training for extreme flight conditions
28.12.2016 | Technical University of Munich (TUM)
Yersiniae cause severe intestinal infections. Studies using Yersinia pseudotuberculosis as a model organism aim to elucidate the infection mechanisms of these...
Researchers from the University of Hamburg in Germany, in collaboration with colleagues from the University of Aarhus in Denmark, have synthesized a new superconducting material by growing a few layers of an antiferromagnetic transition-metal chalcogenide on a bismuth-based topological insulator, both being non-superconducting materials.
While superconductivity and magnetism are generally believed to be mutually exclusive, surprisingly, in this new material, superconducting correlations...
Laser-driving of semimetals allows creating novel quasiparticle states within condensed matter systems and switching between different states on ultrafast time scales
Studying properties of fundamental particles in condensed matter systems is a promising approach to quantum field theory. Quasiparticles offer the opportunity...
Among the general public, solar thermal energy is currently associated with dark blue, rectangular collectors on building roofs. Technologies are needed for aesthetically high quality architecture which offer the architect more room for manoeuvre when it comes to low- and plus-energy buildings. With the “ArKol” project, researchers at Fraunhofer ISE together with partners are currently developing two façade collectors for solar thermal energy generation, which permit a high degree of design flexibility: a strip collector for opaque façade sections and a solar thermal blind for transparent sections. The current state of the two developments will be presented at the BAU 2017 trade fair.
As part of the “ArKol – development of architecturally highly integrated façade collectors with heat pipes” project, Fraunhofer ISE together with its partners...
At TU Wien, an alternative for resource intensive formwork for the construction of concrete domes was developed. It is now used in a test dome for the Austrian Federal Railways Infrastructure (ÖBB Infrastruktur).
Concrete shells are efficient structures, but not very resource efficient. The formwork for the construction of concrete domes alone requires a high amount of...
10.01.2017 | Event News
09.01.2017 | Event News
05.01.2017 | Event News
18.01.2017 | Power and Electrical Engineering
18.01.2017 | Materials Sciences
18.01.2017 | Life Sciences