The Travelling Salesman problem (TSP) is a well-known problem in computer science. Roughly speaking, it refers to a salesperson who must deliver packages in cities that are modelled through a weighted graph, and the objective is to find the optimal route such that the total distance travelled is minimized.
This problem is known for its complexity and for the fact that it is a NP-hard problem, which means that there is no polynomial-time solution (assuming P != NP).
The problem we must solve is, in fact, a specific variant of the TSP, called Vehicle Routing Problem (VRP) which is different from the TSP inasmuch as there are now multiple salespeople (couriers). We will, in addition, add following constraints:
Each courier has a limited space he/she can carry
New orders may appear during the trips, so the
Order may have time-constrained pickup/delivery times: if it can't be picked up/delivered by some time, it's no use.
I can assume I'm given:
A reliable estimate of the time it will take a courier to go from point A to point B
The capacity each courier can carry at any one time (in litres) and the volume of each package.
Other things I can assume
Supposing we have to develop a quick solution just to start off with, without looking at how other people have solved this, here's what I would propose:
These are not optimal solutions. They're just initial solutions that gets the job done quickly.
Our problem can be approached like this:
Given a steady stream of new packages, how to I assign couriers to a) pick up the packages and b) deliver those packages, so as to minimize the total amount of time/distance travelled by the couriers.
I would split the city into a number of non-overlapping sectors and suppose I have some number of couriers either active or waiting in each of those sectors.
Let's assume that orders within those sectors are considered to be "nearby" so that, on average, adding a pickup/deliver order to a courier that's active inside that sector is considered to be acceptable
This also reduces the penalty that a courier incurs if he/she must pickup/deliver orders sequentially, rather than concurrently.
Let's assume that each courier has a delivery list, which are the next orders he/she will fulfill and, when we push an order to a courier, it means that we will add that order to the end of his/her delivery list.
insert an order into an arbitrary place in his/her list (e.g. for time-constrained orders that must be picked-up/delivered at a given time)All other things being equal, we would rather assign a new order to an active courier, so as to avoid him/her becoming inactive.
We need to keep a pool of waiting couriers (for orders no active courier can take) but it must be as small as possible, because it costs money to keep them waiting and, while they are waiting, they don't generate any money for us.
function: get_active_couriers_by_base_sector(x)
return all active couriers who, by the end of their respective order lists, will have x as base area, with couriers with smallest order lists first
function: get_adjacent_areas(x)
return areas which are adjacent to x
for each new order o:
for each area a:
if o is completely within area a:
if o is NOT time-constrained:
couriers <- get_active_couriers_by_base_area(a)
if couriers is not empty:
c <- couriers.get_first()
push o to c
else // no active couriers available in area a
as <- get_adjacent_areas(a)
couriers_in_adjacent_areas <- get_active_couriers_by_base_area(as)
if couriers_in_adjacent_areas is not empty:
c <- couriers_in_adjacent_areas.get_first()
push o to c
else // no available active couriers even in adjacent areas
c <- get_first_waiting_courier()
push o to c
else // o IS time-constrained:
candidate_couriers <- get_active_couriers_by_base_area(a)
if candidate_couriers is not empty
for each active courier c in candidate_couriers:
if all orders after o's pickup time are NOT time-constrained
AND the state of c's trunk supports the addition of a package as large as o:
insert o in c's delivery list, after the first order that
can be picked/up delivered before o's pickup time, given the time estimates
and shift all other orders after that
else: // no candidate couriers in base area a
as <- get_adjacent_areas(a)
candidate_couriers <- get_active_couriers_by_base_area(as)
if candidate_couriers is not empty
for each active courier c in candidate_couriers:
if all orders after o's pickup time are NOT time-constrained
AND the state of c's trunk supports the addition of a package as large as o:
insert o in c's delivery list, after the first order that
can be picked/up delivered before o's pickup time, given the time estimates
and shift all other orders after that
else // no active couriers could be found, even in adjacent areas
c <- get_first_waiting_courier()
push o to c
else: // this order spans multiple areas
a <- o.pickup.get_area()
if O is NOT time-constrained
couriers <- get_active_couriers_by_base_area(a)
if couriers is not empty:
c <- couriers.get_first()
push o to c
else // no active couriers available in area a
as <- get_adjacent_areas(a)
couriers_in_adjacent_areas <- get_active_couriers_by_base_area(as)
if couriers_in_adjacent_areas is not empty:
c <- couriers_in_adjacent_areas.get_first()
push o to c
else // no available active couriers even in adjacent areas
c <- get_first_waiting_courier()
push o to c
else: // order IS time-constrained
candidate_couriers <- get_active_couriers_by_base_area(a)
if candidate_couriers is not empty
for each active courier c in candidate_couriers:
if all orders after o's pickup time are NOT time-constrained
AND the state of c's trunk supports the addition of a package as large as o:
insert o in c's delivery list, after the first order that
can be picked/up delivered before o's pickup time, given the time estimates
and shift all other orders after that
else: // no candidate couriers in base area a
as <- get_adjacent_areas(a)
candidate_couriers <- get_active_couriers_by_base_area(as)
if candidate_couriers is not empty
for each active courier c in candidate_couriers:
if all orders after o's pickup time are NOT time-constrained
AND the state of c's trunk supports the addition of a package as large as o:
insert o in c's delivery list, after the first order that
can be picked/up delivered before o's pickup time, given the time estimates
and shift all other orders after that
else // no active couriers could be found, even in adjacent areas
c <- get_first_waiting_courier()
push o to c
NOTES:
for each new order o:
a <- o.pickup.get_area()
if o is NOT time-constrained:
couriers <- get_active_couriers_by_base_area(a)
if couriers is not empty:
c <- couriers.get_first()
push o to c
else // no active couriers available in area a, so we try in adjacent areas
as <- get_adjacent_areas(a)
couriers_in_adjacent_areas <- get_active_couriers_by_base_area(as)
if couriers_in_adjacent_areas is not empty:
c <- couriers_in_adjacent_areas.get_first()
push o to c
else // no available active couriers even in adjacent areas
c <- get_first_waiting_courier()
push o to c
else // o IS time-constrained:
candidate_couriers <- get_active_couriers_by_base_area(a)
if candidate_couriers is not empty
for each active courier c in candidate_couriers:
if all orders after o's pickup time are NOT time-constrained
AND the state of c's trunk supports the addition of a package as large as o:
insert o in c's delivery list, after the first order that
can be picked/up delivered before o's pickup time, given the time estimates
and shift all other orders after that
else // no active couriers available in area a, so we try in adjacent areas
as <- get_adjacent_areas(a)
candidate_couriers <- get_active_couriers_by_base_area(as)
if candidate_couriers is not empty
for each active courier c in candidate_couriers:
if all orders after o's pickup time are NOT time-constrained
AND the state of c's trunk supports the addition of a package as large as o:
insert o in c's delivery list, after the first order that
can be picked/up delivered before o's pickup time, given the time estimates
and shift all other orders after that
else // no active couriers could be found, even in adjacent areas
c <- get_first_waiting_courier()
push o to c
NOTES:
if too many couriers get too burdened by this algorithm, we can adjust the following:
increase the size of the areas which will probably cause larger delivery queues for each courier
decrease the size of the areas (smaller areas will reduce the coverage area for each courier but may increase the number of order that span multiple areas)
add couriers
in the worst case scenario, we have a time complexity of
the space complexity is as follows:
a list of orders for each active courier - O(N)
a list of couriers - O(N)
a courier may decide to leave with a non-empty delivery list, in which case we must re-assign those orders
If we compare this algorithm to a processor that has to process tasks, each courier would be a processor with a single-core and no multiprocessing capabilities, i.e. it can't have two orders concurrently.
This means that each courier can't interleave orders (as a processor switches between processes that are doing slow tasks such as reading from disk) a courier will sit idle for a long time if we have a time-constrained order where the delivery time is hours or days after the pickup time.
One solution for this is, naturally, to allow each courier (core) to process multiple orders (processes) at the same time, keeping the packages (process context) in memory. We could use the same scheduling mechanisms a processor uses, and watch out for things like starvation.
we could consider dynamic areas, instead of static ones (say a circle with radius d around the courier)
or we could choose better areas, after we collect some data on which areas have more orders
maybe we should calculate the best courier for a given order based upon where that courier will be after the delivery of the last order in his/her queue
Consider cases when it's best for the courier not to pickup/deliver orders sequentially
After looking at a couple of websites and research articles, one comes to the conclusion that, since there is no known way (other than brute forcing all possible paths) to obtain an exact answer for all but trivial problems, one can approach this in one of two ways (stimmt das?)
The vehicle routing problem: State of the art classification and review
Vehicle routing problems with loading constraints: state-of-the-art and future directions
The Vehicle Routing Problem: An overview of exact and approximate algorithms