PHP Classes
elePHPant
Icontem

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

Recommend this page to a friend!
  Info   View files View files (14)   DownloadInstall with Composer Download .zip   Reputation   Support forum (1)   Blog    
Last Updated Ratings Unique User Downloads Download Rankings
2013-09-04 (2 years ago) RSS 2.0 feedNot enough user ratingsTotal: 315 All time: 6,809 This week: 1,134Up
Version License PHP version Categories
matrix-cw 1.0.0GNU General Publi...5.3Algorithms
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
PHP Programming Innovation award nominee
July 2013
Number 7


Prize: 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
Picture of Benjamin Vatter
  Performance   Level  
Name: Benjamin Vatter <contact>
Classes: 1 package by
Country: Chile Chile
Age: 25
All time rank: 350913 in Chile Chile
Week rank: 1488 Up5 in Chile Chile Up
Innovation award
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 folder image Files  
File Role Description
Files folder imageexample (12 files)
Accessible without login Plain text file further_development.txt Doc. for further development
Accessible without login Plain text file readme.txt Doc. general readme

  Files folder image Files  /  example  
File Role Description
  Accessible without login Plain text file clientes.csv Data client data
  Accessible without login Plain text file data.php Aux. data load
  Accessible without login Plain text file distance1.csv Data distance matrix part 1
  Accessible without login Plain text file distance2.csv Data distance matrix part 2
  Plain text file matrix.php Class auxiliary class
  Plain text file matrixcw.php Class main class
  Accessible without login Plain text file matrixpararun.php Example parametric run of the class
  Accessible without login Plain text file matrixrun.php Example normal run of the class
  Accessible without login Plain text file readme.txt Doc. read before executing
  Accessible without login Plain text file trucks.csv Data truck data
  Accessible without login Plain text file trucksn.csv Data trucks data
  Accessible without login Plain text file trucksn.php Data data of the trucks

 Version Control Unique User Downloads Download Rankings  
 0%
Total:315
This week:0
All time:6,809
This week:1,134Up
User Comments (1)