How to sort locations by distance with constraint that pickup location must go before delivery location

Question

I was wondering if there is solution to sort Locations by distance from first reference location but respecting constraint that pickup location should be placed before delivery location.

I was thinking if it is even possible as pickup location of one order can be delivery of other order and if we have two orders where pickup and delivery locations are reversed (A order's pickup location equals B order's delivery location and A order's delivery location equals B order's pickup location) then it will never meet constraint.

Below is code for sorting locations by distance, but not respecting constraint of pickup before delivery. It is rough one as probably graphs should be used for better result.

Am I right that it's probably impossible to solve with these constraints?

interface Order {
    id: number;
    pickup: Location;
    delivery: Location;
}

interface Location {
    id: number;
    latitude: number;
    longitude: number;
}

// Function to calculate distance using the Haversine formula
function getDistance(loc1: Location, loc2: Location): number {
/** Implementation not important here **/
}

function getSortedUniqueLocations(orderArray: Order[]): Location[] {
    if (orderArray.length === 0) return [];

    const uniqueLocations = new Map<string, Location>();

    for (let i = 0; i < orderArray.length; i++) {
        const order = orderArray[i];
        const pickup = order.pickup;
        const delivery = order.delivery;

        const pickupKey = `${pickup.latitude},${pickup.longitude}`;
        const deliveryKey = `${delivery.latitude},${delivery.longitude}`;

        if (!uniqueLocations.has(pickupKey)) {
            uniqueLocations.set(pickupKey, pickup);
        }
        if (!uniqueLocations.has(deliveryKey)) {
            uniqueLocations.set(deliveryKey, delivery);
        }
    }

    const locations = Array.from(uniqueLocations.values());

    const firstLocation = orderArray[0].pickup;
    locations.sort((a, b) => getDistance(firstLocation, a) - getDistance(firstLocation, b));

    return locations;
}

Answer 1

You could create the graph with as vertices the locations and directed edges linking pickup locations with destinations.

Then find all the nodes of this graph that have no incoming edge: these are all candidate to appear as first location in the end result. Put those in a priority queue, keyed by distance. Then repeat until the priority queue is empty:

• Pull the node with the least distance from the priority queue
• Append this location to the end result
• Remove this node with its edges from the graph -- this can make some other nodes to end up without incoming edges
• Add any nodes without incoming edges to the priority queue

First, here is a binary heap implementation you could use as priority queue:

type Comparator<T> = (a: T, b: T) => number;

class Heap<T> {
    private heap: T[] = [];
    private comparator: Comparator<T>;

    constructor(comparator: Comparator<T>, data: T[] = []) {
        this.comparator = comparator;
        this.heap = data;
        this.heapify();
    }    

    siftDown(i=0, value=this.heap[i]) {
        if (i < this.heap.length) {
            while (true) {
                let j = i*2 + 1;
                if (j + 1 < this.heap.length && this.comparator(this.heap[j], this.heap[j+1]) > 0) {
                    j++;
                }
                if (j >= this.heap.length || this.comparator(value, this.heap[j]) < 0) break;
                this.heap[i] = this.heap[j];
                i = j;
            }
            this.heap[i] = value
        }
    }
    heapify() {
        for (let i = this.heap.length >> 1; i--; ) {
            this.siftDown(i);
        }
    }
    pop() {
        return this.exchange(this.heap.pop()!);
    }
    exchange(value: T) {
        if (!this.heap.length) return value;
        let topValue = this.heap[0];
        this.siftDown(0, value);
        return topValue;
    }
    push(value: T) {
        let i = this.heap.length,
            j;
        while ((j = (i - 1) >> 1) >= 0 && this.comparator(value, this.heap[j]) < 0) {
            this.heap[i] = this.heap[j];
            i = j;
        }
        this.heap[i] = value;
    }
    isEmpty() {
        return !this.heap.length;
    }
}

Then the rest of the code could be:

interface Order {
    id: number;
    pickup: Location;
    delivery: Location;
}

interface Location {
    id: number;
    latitude: number;
    longitude: number;
}

interface Node {
    location: Location;
    sources: Set<Node>;
    destinations: Set<Node>;
    distance: number;
}

function getDistance(loc1: Location, loc2: Location): number {
    // Simplified Implementation
    return ((loc1.latitude - loc2.latitude) ** 2 + (loc1.longitude - loc2.longitude) ** 2) ** 0.5;
}

function getSortedUniqueLocations(orderArray: Order[]): Location[] {
    if (orderArray.length === 0) return [];

    const firstLocation = orderArray[0].pickup;
    
    const locationsById: Map<number, Node> = new Map();

    // Get all locations
    for (const order of orderArray) {
        locationsById.set(order.pickup.id, { location: order.pickup, sources: new Set(), destinations: new Set(), distance: 0 } as Node);
        locationsById.set(order.delivery.id, { location: order.delivery, sources: new Set(), destinations: new Set(), distance: 0 } as Node);
    }
    // Populate adjacency list
    for (const order of orderArray) {
        const pickup: Node = locationsById.get(order.pickup.id)!;
        const delivery: Node = locationsById.get(order.delivery.id)!;
        pickup.destinations.add(delivery);
        delivery.sources.add(pickup);
    }
    // Translate to use location objects as keys (no more use of id)
    const nodes: Set<Node> = new Set(locationsById.values());
    // Set distances, and queue locations to which there are no deliveries pending
    const heap = new Heap((a: Node, b: Node) => a.distance - b.distance);
    for (const node of nodes) {
        node.distance = getDistance(firstLocation, node.location);
        if (node.sources.size === 0) heap.push(node); 
    }
    // Main loop
    const locations = [];
    while (!heap.isEmpty()) {
        const node = heap.pop();
        locations.push(node.location);
        for (const destination of node.destinations) {
            destination.sources.delete(node);
            if (destination.sources.size === 0) {
                heap.push(destination); 
            }
        }
    }
    return locations;
}

Example run

I took this graph as test input:

Coordinates are integers (0..4), and arrows are the dependencies of pickups to destinations.

Here is the initialisation of that example, the execution of the algorithm on it, and the output loop:

// Create example input
const locations: Location[] = Array.from({length: 25}, (_, id) => {
    return {id, latitude: Math.floor(id / 5), longitude: id % 5 } as Location;
});

const orderArray: Order[] = [
    [0, 7], [2, 8], [3, 12],
    [5, 1], [8, 11], [9, 3],
    [10, 5], [11, 6], [11, 16], [12, 23], [13, 4], [14, 13], [14, 19],
    [15, 21], [17, 10], [18, 7], [18, 21], [19, 23],
    [20, 16], [22, 13], [24, 18],
].map(([pickup, delivery], id) => { 
    return { id, pickup: locations[pickup], delivery: locations[delivery] };
});
const orderedLocations = getSortedUniqueLocations(orderArray);

if (orderedLocations.length < locations.length) {
    console.log("Circular dependencies: there is no solution");
} else {
    console.log("results:");
    for (const location of orderedLocations) {
        console.log(JSON.stringify(location));
    }
}

This outputs:

{"id":0,"latitude":0,"longitude":0}
{"id":2,"latitude":0,"longitude":2} 
{"id":15,"latitude":3,"longitude":0}
{"id":8,"latitude":1,"longitude":3}
{"id":11,"latitude":2,"longitude":1}
{"id":6,"latitude":1,"longitude":1}
{"id":17,"latitude":3,"longitude":2}
{"id":10,"latitude":2,"longitude":0}
{"id":5,"latitude":1,"longitude":0}
{"id":1,"latitude":0,"longitude":1}
{"id":20,"latitude":4,"longitude":0}
{"id":16,"latitude":3,"longitude":1}
{"id":9,"latitude":1,"longitude":4}
{"id":3,"latitude":0,"longitude":3}
{"id":12,"latitude":2,"longitude":2}
{"id":22,"latitude":4,"longitude":2}
{"id":14,"latitude":2,"longitude":4}
{"id":13,"latitude":2,"longitude":3}
{"id":4,"latitude":0,"longitude":4}
{"id":19,"latitude":3,"longitude":4}
{"id":23,"latitude":4,"longitude":3}
{"id":24,"latitude":4,"longitude":4}
{"id":18,"latitude":3,"longitude":3}
{"id":7,"latitude":1,"longitude":2}
{"id":21,"latitude":4,"longitude":1}

Limitations

As you have indicated, if the graph has loops, then there is no solution. The above algorithm would only put nodes in the priority queue nodes that are not part of any loops, and so the result would be incomplete. When that is detected, a message is output that there is no solution.

Answer 2

This will not always be possible.

For example with 2 locations, A and B and 2 deliveries A->B, B->A, you can't even obey both constraints and that's before you insist they be sorted by distance.

You'll need to decide what matters more and build the algorithm for the probable contradictions.

An example alternative could be:

1. Sort by distance
2. Use constraints only to break ties in distance
3. Test all constraints
4. Throw an error if a constraint is broken

But that choice prioritises sorting by distances and will throw errors even when it is working correctly (which will need to be handled). You'll need to decide on your own priorities and behaviour.