Computer solution to delivery problem

Oct 18, 2007

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.

Source: Inderscience Publishers

Explore further: Non-emergency lines still need a back up plan in case of another meltdown

add to favorites email to friend print save as pdf

Related Stories

From video camera to driverless shuttle vehicle

Nov 12, 2014

A new type of driverless shuttle vehicle has been developed thanks to innovative computer vision guidance technology that enables the vehicle to locate itself on a roadway reliably and inexpensively. The ...

Tech-friendly cities struggle with new biz rules (Update)

Sep 28, 2014

A renowned technology hub that is home to some of the country's top universities, Boston is emerging as an unlikely battleground for web-based businesses like Airbnb and Uber, with some saying more regulations ...

US names New York test site for small drones

Aug 08, 2014

The Federal Aviation Administration (FAA) announced Thursday a fifth test site for small drones, as it continues to hammer out regulations for their use in US airspace.

The traffic light turns 100

Aug 06, 2014

100 years ago, on August 5, 1914, the first electric traffic light was installed on a city street in Cleveland, Ohio. Siemens entered the business ten years later, when the first traffic light tower from Siemens was installed ...

Recommended for you

Namibia prepares for Africa's first e-vote

Nov 26, 2014

Namibia will vote in Africa's first electronic ballot Friday, a general election that will usher in a new president and quotas to put more women in government.

US agency threatens to act against air bag maker

Nov 26, 2014

A dispute between U.S. safety regulators and air bag maker Takata Corp. escalated Wednesday when the government threatened fines and legal action unless the company admits that driver's air bag inflators ...

Japan orders air bag maker to conduct probe

Nov 21, 2014

Japan's transport ministry said Friday it has ordered air bag maker Takata to conduct an internal investigation after cases of its air bags exploding triggered safety concerns in the United States and other countries.

Senators get no clear answers on air bag safety

Nov 20, 2014

There were apologies and long-winded explanations, but after nearly four hours of testimony about exploding air bags, senators never got a clear answer to the question most people have: whether or not their ...

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.