LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 April 19 2012

geek
Member

[Exercise] Delivery Center

You are in charge of a delivery center with a fixed number of drivers that dispatches orders in batch mode (multiple orders at a time). Every order has an associated (2D) position on the map. You are aware of the position of the center and you know that every one of the drivers can carry all the deliverables at once.

Find an assignment of orders to drivers that minimizes the total distance traveled by the drivers for a given batch. Note that the delivery center existed in an age when the Earth was flat.

Simple samples:

3 (0, 0) 2 (1, 0) (-1, 0)

0: (-1, 0)
1: (1, 0)
3 (0, 0) 2 (1, 0) (2, 0)

0: (1, 0) (2, 0)

Last edited by geek (April 19 2012)

Offline

#2 April 20 2012

arithma
Member

Re: [Exercise] Delivery Center

In the first sample, 3 is the number of drivers, (0,0) is the location of the center, 2 is number of orders and the (1,0) and (-1,0) are the locations?
Every sample is the whole batch as well, right?
The drivers can only travel on the horizontal and vertical grids? or can they go through diagonals?

Cool exercise, going to go through it in the weekend hopefully.

Offline

#3 April 20 2012

geek
Member

Re: [Exercise] Delivery Center

@arithma: true. let's allow the drivers to move in any direction, for now.

Offline

#4 April 21 2012

arithma
Member

Re: [Exercise] Delivery Center

Travelling Salesman is NP. So intuitively Travelling salesmen are NP too (I don't have a proof, so could be wrong). The former is a special case of the latter, so obviously it is at least NP. As far as I remember the diagrams on Wiki, complexity categories are ordered.

The problem would be much more fun if we took heuristics out on the field and not searched for the absolute correct answer (minimum).

Last edited by arithma (April 21 2012)

Offline

#5 April 21 2012

Joe
Member

Re: [Exercise] Delivery Center

Here's my solution.

#!/usr/bin/python2.7

from math import sqrt


def distance(driver, order):
    '''each argument is a tuple indicating the position of the driver and the
    order respectively. It returns a numerical value of the distance between
    them'''

    # I'm sure there's a square function defined somewehere.
    sq = lambda x: x*x


    return sqrt(sq(driver[0] - order[0]) +
		sq(driver[1] - order[1]))

def calc_all_distances(drivers, orders):
    '''drivers and order are lists of tuples.
    This function will calculate all the distances between each driver and
    each order.

    It will then store the result in a dictionary where the keys are tuples
    of the indexes of each element.

    For instance: distances[(0, 2)] is the distance between driver[0] and 
    order[2].'''
    
    return {(i, j): distance(drivers[i], orders[j]) for i in xrange(len(drivers))
                                                    for j in xrange(len(orders))}
   

def return_min_dist(distances):
    '''the input is a dictionary return by calc_all_distances.
    The function returns the key of the smallest of value.'''

    min(distances, key=distances.get)


def move_driv(drivers, idx, newpos):
    '''update position of drivers[idx]'''
    
    drivers[idx] = newpos
    return drivers

        
def deliv(drivers, orders, driv_ord):

    '''The programs main loop.

    It starts by calculating all the distances between drivers and orders.
    then looks for the shortest distance.

    Repeat until all orders are selected.'''
    
    if len(orders) == 0:
	return driv_ord

    distances = calc_all_distances(drivers, orders)
    shortest = return_min_dist(distances)

    mvdriver = shortest[0]
    mvposition = shortest[1]

    newpos = orders[mvposition]
    driv_ord[mvdriver].append(orders[mvposition])
    orders.pop(mvposition)

    return deliv(move_driv(drivers, mvdriver, newpos),
		 orders,
		 driv_ord)


def test (nbrdrivers, shop_location, orders):
    '''nbrdrivers is an int.
       shop_location is a tuple of coordiantes,
       orders is a list of tuples.'''
    
    drivers = [shop_location] * nbrdrivers
    dr_ord = [[] for n in range(nbrdrivers)]

    return deliv(drivers, orders, dr_ord)


print test(3, 
	   (0, 0), 
	   [(0, 1), (0, -1)])

print test(3,
	   (0, 0),
	   [(0, 1), (0, 2)])

Output:

[[(0, -1)], [], [(0, 1)]]
[[(0, 1), (0, 2)], [], []]

It simply consists of bruteforcing by calculating all the distances between orders and drivers and selecting the shortest one each time.

The code is valid for geek's examples, although I would be surprised if it is the definite general solution to the problem.

I commented the code so that I could get feedback. Don't hesitate to bash it.

Last edited by Joe (April 23 2012)

Offline

#6 April 21 2012

geek
Member

Re: [Exercise] Delivery Center

counter-example:
S3Ubo.png

Offline

#7 April 23 2012

arithma
Member

Re: [Exercise] Delivery Center

Tested on a fairly trivial example.
The drivers don't go home.

//
//  main.cpp
//  Drivers
//
//  Created by Mohammad Skafi on 4/22/12.
//

#include <vector>
#include <set>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct Coord{
    int x, y;
    
    Coord() : x(0), y(0) {}
    Coord(int _x, int _y) : x(_x), y(_y) {}
    
    bool operator==(Coord const &other) const{
        return x == other.x && y == other.y;
    }
    
    bool operator<(Coord const &other) const{
        return (x < other.x) || ((x == other.x) && (y < other.y));
    }
};

double distance(Coord coord1, Coord coord2){
    int diffX = coord1.x - coord2.x;
    int diffY = coord2.y - coord2.y;
    return sqrt(diffX*diffX + diffY*diffY);
}

struct Move{
    Coord from;
    Coord to;
};

struct Node;
struct NeighborNode;

struct Node{
    vector<Coord> drivers;
    vector<Coord> deliveries;
};

struct NeighborNode {
    Node node;
    Move move;
    double distance;
};

vector<NeighborNode> neighbors(Node node)
{
    vector<NeighborNode> result;
    
    set<Coord> uniques(node.drivers.begin(), node.drivers.end());
    for(auto driverItr = uniques.begin(); driverItr != uniques.end(); driverItr++){
        for(auto deliveryItr = node.deliveries.begin(); deliveryItr != node.deliveries.end(); deliveryItr++){
            NeighborNode neighbor;
            neighbor.node = node;
            
            auto driver = find(neighbor.node.drivers.begin(), neighbor.node.drivers.end(), *driverItr);
            *driver = *deliveryItr;
            
            neighbor.node.deliveries.erase(neighbor.node.deliveries.begin() + (deliveryItr - node.deliveries.begin()));
            
            neighbor.distance = ::distance(*driverItr, *deliveryItr);
            Move move = { *driverItr, *deliveryItr };
            neighbor.move = move;
            
            result.push_back(neighbor);
        }
    }
    
    return result;
}

double heuristic(Node const &node){
    set<Coord> uniques(node.drivers.begin(), node.drivers.end());
    double min = 1e200;
    for(auto driverItr = uniques.begin(); driverItr != uniques.end(); driverItr++){
        double max = 0;
        for(auto deliveryItr = node.deliveries.begin(); deliveryItr != node.deliveries.end(); deliveryItr++){
            double d = ::distance(*driverItr, *deliveryItr);
            if(d>max)
                max = d;
        }
        if(max < min)
            min = max;
    }
    return min;
}

struct SearchNode{
    Node node;
    vector<Move> moves;
    vector<Node> states;
    double cost;
    double estimate;
};

SearchNode breadth_first(Node start, double (heuristic)(Node const &)) {
    vector<SearchNode> breadth;
    
    SearchNode startSearch;
    startSearch.node = start;
    startSearch.estimate = heuristic(start);
    breadth.push_back(startSearch);
    
    for(;;){
        int min_node = 0;
        double estimate = breadth[0].estimate;
        
        for(int i = 1; i < breadth.size(); i++){
            if(breadth[i].estimate < estimate){
                min_node = i;
                estimate = breadth[i].estimate;
            }
        }
        
        SearchNode min = breadth[min_node];
        if(min.node.deliveries.size() == 0)
            return min;
        
        breadth.erase(breadth.begin() + min_node);
        
        auto neighs = neighbors(min.node);
        for(auto itr = neighs.begin(); itr != neighs.end(); itr++){
            SearchNode child;
            
            child.node = itr->node;
            
            child.cost = min.cost + itr->distance;
            
            child.estimate = min.cost + heuristic(child.node);
            
            child.states = min.states;
            child.states.push_back(min.node);
            
            child.moves = min.moves;
            child.moves.push_back(itr->move);
            
            breadth.push_back(child);
        }
    }
}

int main(int argc, const char * argv[])
{
    Node start;
    start.drivers.push_back(Coord(0, 0));
    start.drivers.push_back(Coord(0, 0));
    start.deliveries.push_back(Coord(1,0));
    start.deliveries.push_back(Coord(2,1));
    start.deliveries.push_back(Coord(0,1));
    SearchNode search = breadth_first(start, heuristic);
    for(int i = 0; i < search.moves.size(); i++){
        cout << "From: " << search.moves[i].from.x << ", " << search.moves[i].from.y << endl;
        cout << "To:   " << search.moves[i].to.x << ", " << search.moves[i].to.y << endl;
    }
    return 0;
}

Last edited by arithma (April 23 2012)

Offline

#8 April 23 2012

geek
Member

Re: [Exercise] Delivery Center

going back home is what makes this problem interesting. if this constraint is removed, the problem reduces to finding an Euclidean minimum spanning tree with an upper bound on the degree of the source (number of drivers available). this is what @rahmu's algorithm does using Prim's algorithm for computing the MST.

Offline

#9 April 23 2012

arithma
Member

Re: [Exercise] Delivery Center

rahmu's solution is steepest decent (greedy). I have been thinking about the return home nevertheless and guess it could be included into the heuristic anyway.
We need a way to test case our solutions. Maybe they're fucked up beyond recognition.

Offline

#10 April 23 2012

Joe
Member

Re: [Exercise] Delivery Center

You guys are making my code sound a lot fancier than what it actually is: me acting on a hunch. I don't have any science to back up my algo (apparently @geek has  ).

For the record, I had not considered the drivers returning home. In all fairness it wasn't mentionned in the original post, although I admit it's what makes the exercise challenging. I also admit I have no idea how to solve the problem then.

@arithma, I was interested in how your code improves mine, but I got too caught up with syntax idiocracies of c++ that I really don't have the courage to go through it. The following line in particular makes me dazed and confused:

SearchNode breadth_first(Node start, double (heuristic)(Node const &))

Also, if Coord is defining functions inside its definition why is it a struct not a class? (Okay, this one is just a nitpick. I honestly did not understand the definition of the function above).

At least your code intoduced me to the shiny new auto keyword which to me feels like C++ admitting that dynamic typing isn't that bad an idea after all (ironic isn't it?).

Finally I updated my code. Not to make it more clever or performant (or more relevant to the problem at hand -- drivers return home), but to make syntax changes that I find stylistically more elegant (using dictionary comprehension and a cool use of function min()). Call me artistically shallow, but I'm much more interested by this aesthetic nonsense than the actual core of the problem.

@geek: I know you're cooking up a crazy Mathematica one-liner, but this time could you please write something understandable by ... you know... anyone who's not a math genius? ;)

Offline

#11 April 23 2012

arithma
Member

Re: [Exercise] Delivery Center

@rahmu:

double (heuristic)(Node const &)

This is not necessary at all. Now that I remember that I have it makes me laugh at how I was crying in the middle of the night at templates breaking all over the place. I was trying to seperate the "breadth searching" from the node structure, but the template errors became crazy (I wasn't concentrating much either.)

SearchNode is a graph node with a trail on how we came to this place.

The auto keyword is not dynamic typing. It's type inference. A much different beast. It helps with such kinds of problems because it really protects against the stupid mistakes that can be really hard to catch.

I missed to answer the struct thing. In C++, struct is the same thing as class with the different property of having everything public by default.

Last edited by arithma (April 23 2012)

Offline

#12 April 23 2012

Joe
Member

Re: [Exercise] Delivery Center

The auto keyword is not dynamic typing. It's type inference. A much different beast.

Thanks for pointing out the difference. For what it's worth, this article makes a strong case of showing the difference between the two.

Offline

#13 April 23 2012

arithma
Member

Re: [Exercise] Delivery Center

So changing the heuristic into the following, makes the solution correct for going back home.

double heuristic(Node const &node){
    double costHome = 0;
    Coord home;
    for(auto driverItr = node.drivers.begin(); driverItr !=  node.drivers.end(); driverItr++){
        costHome += ::distance(*driverItr, home);
    }
    set<Coord> uniques(node.drivers.begin(), node.drivers.end());
    double min = 1e200;
    for(auto driverItr = uniques.begin(); driverItr != uniques.end(); driverItr++){
        double max = 0;
        for(auto deliveryItr = node.deliveries.begin(); deliveryItr != node.deliveries.end(); deliveryItr++){
            double cost = costHome;
            cost -= ::distance(*driverItr, home);
            cost += ::distance(*driverItr, *deliveryItr);
            cost += ::distance(*deliveryItr, home);
            if(cost>max){
                max = cost;
            }
        }
        if(max < min)
            min = max;
    }
    return min;
}

I didn't add the steps to go back home for the drivers but they're implied.

Last edited by arithma (April 23 2012)

Offline

#14 April 23 2012

arithma
Member

Re: [Exercise] Delivery Center

The above is wrong.

edit: Corrected.

double distance(Coord coord1, Coord coord2){
    int diffX = coord1.x - coord2.x;
    int diffY = coord1.y - coord2.y;
    return sqrt(diffX*diffX + diffY*diffY);
}

Last edited by arithma (April 23 2012)

Offline

#15 April 27 2012

arithma
Member

Re: [Exercise] Delivery Center

This exercise would be fun if we allow two players. We'd need a grid instead of our current setting. Each driver can move on a single grid border (be it a hex, square grid, or octagonal). Each player can issue as much commands to their drivers as they need (they'll move just a single unit regardless).

Offline

Board footer