PHP ordering array into groups

Question

I have a logistic app in PHP that determines auto routes for orders. For that, we have a matrix of routes and route points, where the points in the route could be in more than one route. So, we could have defined routes like this:

Route1 = ['Depo','City 1','City 3','City 4']
Route2 = ['Depo','City 1','City 2','City 3', 'City 5']
Route3 = ['Depo','City 2','City4','City 5']

The routes are fixed, the points from route are defined from the nearest to the farest point from the 'Depo' warehouse The planner selects from orders the lines that have to be delivered, and the app fires one array with points for delivery like this:

['City 1','City 3','City 4','City 2', 'City 1', 'City 3', 'City 2', 'City 5','City 1']

The question: How could I get to determine the ideal route for given array? I want the result to take into consideration the fact that an ideal route is the one with most points covered. The system could fire a result with more than one route, in this case, let's say the result could be Route 1 and Route 2

If anyone needs more details just comment Thanks!

I don't understand: you say routes are fixed, but the you want to compute a new ideal route going through several points? Apart from that, reminds me very much of the Travelling Salesman Problem — instanceofnull
– instanceofnull, Commented Mar 15, 2015 at 7:44
No, you misunderstood.. I never said I want to compute a new ideal route, I want the app to determine from that array wich of the given routes is the best to deliver.. by keeping in mind that the route determined is covered by as many as possible points — rosuandreimihai
– rosuandreimihai, Commented Mar 15, 2015 at 7:47
The TSP is not ok for what I desire, I have fixed routes, so the ideal route with shortest distance is not to be taken into consideration — rosuandreimihai
– rosuandreimihai, Commented Mar 15, 2015 at 7:51
So you want to select which of the fixed routes covers the highest percentage of sites in the given array, right? — instanceofnull
– instanceofnull, Commented Mar 15, 2015 at 8:04

skroczek · Accepted Answer · 2015-03-15 08:35:13Z

This function is not perfect, but it could be used as a base to build the own algorithm:

<?php

function determRoute(array $routes, $order)
{
    // Because the same destination can occur multiple times we build a "factor" array.
    $orderFactor = array_count_values($order);
    $routeScores = array();

    // We iterate over the routes
    foreach ($routes as $key => $r) {
        foreach ($orderFactor as $i => $f) {
            // And if the destination exists in the route we add the factor
            if (in_array($i, $r)) {
                $routeScores[$key] = $routeScores[$key] + $f;
            }
        }

    }

    arsort($routeScores);
    reset($routeScores);

    // return the first array key with the highest score
    return key($routeScores);

}

$routes['route1'] = ['Depo', 'City 1', 'City 3', 'City 4'];
$routes['route2'] = ['Depo', 'City 1', 'City 2', 'City 3', 'City 5'];
$routes['route3'] = ['Depo', 'City 2', 'City4', 'City 5'];


$order = ['City 1', 'City 3', 'City 4', 'City 2', 'City 1', 'City 3', 'City 2', 'City 5', 'City 1'];

while (0 !== count($order)) {
    $resultRouteKey = determRoute($routes, $order);
    $resultRouteKeys[] = $resultRouteKey;
    $order = array_diff($order, $routes[$resultRouteKey]);
}
var_dump($resultRouteKeys);

/**
The output is:
array(2) {
  [0] =>
  string(6) "route2"
  [1] =>
  string(6) "route1"
}
*/

instanceofnull · Accepted Answer · 2015-03-15 08:15:32Z

1

If I understand you correctly, the only relevant information in routes is the cities they visit, not their order. A very straightforward implementation would be something like this. Note there's plenty of room for optimization:

$routes = [
    'route1' => ['Depo', 'City 1', ...],
    'route2' => ['Depo', 'City 2', ...],
    ...
];
$target = ['City 1','City 3','City 4','City 2', 'City 1', 'City 3', 'City 2', 'City 5','City 1'];

$target_point_count = array_count_values($target);
$best_route = null;
$best_score = 0;

foreach($routes as $route => $points) {
    $route_score = 0;
    foreach($points as $point) {
       $route_score += intval($target_point_count[$point]);
    }
    if($route_score > $best_score) {
        $best_route = $route;
        $best_score = $route_score;
    }
}

answered Mar 15, 2015 at 8:15

instanceofnull

1,0811 gold badge7 silver badges15 bronze badges

3 Comments

rosuandreimihai Over a year ago

The order of points (cities) visited is extremely important, the routes are defined keeping in mind the nearest and the farest location

rosuandreimihai Over a year ago

The iteration above would give one single route for delivery, but it would not cover all points in the target.. The dilemma was how to figure out the best routes for delivery from multiple variants. Actually, the real system has more than 200 routes and over 1000 points inside routes

instanceofnull Over a year ago

You should really describe the problem more precisely. This is the first time I learn that the expected output is a set of routes, and not a single one. Specifically, what makes a solution ideal? The one containing the least routes?

Collectives™ on Stack Overflow

PHP ordering array into groups

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related