# PHP Clarke and Wright Algorithm: Solve a truck routing problem with Clarke & Wright

 Version License PHP version Categories matrix-cw 1.0.0 GNU General Publi... 5.3 Algorithms
Description Author

This class can solve a truck routing problem with the Clarke and Wright algorithm.

It attempts to solve the problem of determining the routes of a given number of trucks with different weight and volume capacity will be dispatching deliveries to a certain number of clients distributed geographically within certain time windows.

The class takes as parameters the nodes of positions of each client, the demands of each client, a matrix of distance between nodes and the capacity of each truck.

It computes the route for each truck, as well the time and distance to drive to each customer, and the volume and weight to transport.

Innovation Award
 July 2013 Number 7Prize: One copy of DWebPro Standard License The problem of a distribution business that needs to deliver packages to multiple customers in different locations is classic. This class provides an optimized solution to calculate routes of trucks to deliver packages. Manuel Lemos
 Performance Level
Name: Classes: Benjamin Vatter `` 1 package by Benjamin Vatter Chile 26 3493 13 in Chile 1482 6 in Chile
Innovation award

Nominee: 1x

Details
 ```This is a Clarke & Wright Savings algorithm adapted for asymmetric distance (or cost) matrix and under a simple time window scenario. It was created as part for the IN4704 at the University of Chile. The scenario is described as N trucks with different weight and volume capacity have to dispatch to M different clients geographically distributed across town. Those clients can be of 4 types N,M,S and C, each client type has a time window in which it can be served and a specific service time. The time between different nodes is calculated considering an average of 30km/h driving speed for the trucks. The Clarke and Wright algorithm is pretty simple and standard. The truck assignment method is more complex and proceeds as follows: 1) For each route we create a list of trucks capable of transporting the demand. 2) If a route has a possible truck that isnâ€™t already in use by another route, it is assigned to it. 3) If there is no free truck for the route a pseudo-matrix of 1 and 0 is created where the rows are the trucks and the columns are the routes. A 1 is assigned if the route and truck can be matched. 4) Then we simulate a pivoting process on the columns of the matrix until a strictly positive diagonal is formed, giving a solution for the problem. (This pivoting is done by deleting and recreating rows and columns of the matrix, due to the mathematical restrictions of php. Also a custom Matrix class is created for simplicity). Notice that no client node can be duplicate. we give an example of how to correct this in data.php. It was programmed in php for speed and simplicity of writing and reading, not calculating optimality. The code is not intended to be perfect in any terms, just the simplest of approach to the heuristic proposed for the problem by Clarke & Wright (1964) and adapted to asymmetric scenario by Paessens (1988). Programmed by B. Vatter Model adapted by A Martinez, P. Oyarzun, B. Vatter Special thanks to Ron Cairns for testing the class and noticing the missing files. Special thanks to Ron Cairn use, copy, further develop and hopefuly share again :)```
 Files
File Role Description
example (12 files)
further_development.txt Doc. for further development

 Files / example
File Role Description
clientes.csv Data client data
distance1.csv Data distance matrix part 1
distance2.csv Data distance matrix part 2
matrix.php Class auxiliary class
matrixcw.php Class main class
matrixpararun.php Example parametric run of the class
matrixrun.php Example normal run of the class
trucks.csv Data truck data
trucksn.csv Data trucks data
trucksn.php Data data of the trucks

0%
 Total: 330 This week: 0
 All time: 6,740 This week: 507
All time 83% 91% 58% 91% - - 65% 571

 This class is directly applicable to the scrap metal/paper/gl...2 years ago (ron dandy) 77%