Given multiple job locations, and multiple driver locations, what is
the best algorithm or approach to solve the problem of allocating jobs
to the drivers so that overall fleet costs are minimised.

+ Assume drivers each have a designated home location (Location may be
shared with other drivers)
+ Assume drivers cost $30 / hr and 50c/km with a minimum engagement of
4hrs. Overtime is costed at double time for a maximum shift of 12hrs
in a day
+ Assume there are at least 100 job destinations and 5 drivers, IE the
solution cannot be realistically done via brute force
+ The solution should be calculated within a reasonable time such as
several minutes or less, and does not need to be the absolute optimum,
but rather the best approximation of optimum

Consider my own suggested solution below. It may work, but perhaps you
know of a much better way to solve this real-world problem?
-----------------------------------------------------------------------------

The ?travelling salesman? problem (TSP) is where we try to determine
the optimal route sequence, which can only be solved by brute force
for a very small number of destinations. For ten destinations however,
we may find the application requiring a year to compute the answer,
due to the exponential growth in processing time for each new
destination.
Optimising fleet runs is a difficult process, as it involves more
variables, being the number and location of drivers or depots. The
application must not only solve the TSP for each driver, it must also
allocate job destinations to each driver in the first place.

ADVANTAGES
Optimising the job allocation to drivers allows:
1.	Optimise fleet costs with lower kilometres travelled, as well as
driver hours etc
2.	Increase response time to jobs
3.	Happier drivers working closer to their (known) home area
4.	Manage driver workloads, enable equal share of work to drivers, or
alternatively manage various staff at different work levels, such as
part time staff allocated less work

RUN CUTTING
1.	Analyse all jobs and all available staff
2.	Calculate the maximum distance from each job to each staff member
3.	Allocate the furthest job to the closest staff member, provided
they are available and have capacity to take the job
4.	Continue above until all jobs are allocated
5.	When a staff member is at capacity, they cannot be allocated any
more work, so others nearby must take these jobs ? IE continue process
assuming they don?t exist
6.	Finish initial allocation, assuming there is sufficient staff to
cover the available jobs. Consider holding some jobs to another day if
required
7.	Look at workloads of staff
8.	Reallocate jobs to better apportion the workloads as required
9.	Commence optimisation
a.	For each allocated job, test the situation if this job was to be
allocated to another staff member.
b.	Test reallocate more and more jobs, weighted to nearby staff areas
c.	Analyse how closely the workloads fit optimal proportions, as well
as optimising overall fleet costs of km and wages
10.	Complete destination allocation
11.	Commence destination sequencing (TSP)
12.	Process complete. Provide staff with their allocated jobs and runs

CENTRAL DEPARTURE POINT
The above algorithm works well, but as the departure points merge or
become common, the algorithm fails, as it cannot correctly apportion
runs to drivers by area, as there is no variation in areas when all
drivers depart from a common point. In this case we need to establish
run vectors, which define the average weighted direction of all jobs
for a given run.

1.	Plot all job points & base departure point
2.	Take job#1, and draw a vector from base to job#1. This defines the
first test vector for run#1 (Temp_Run1)
3.	Take job#2 & draw vector from base to job#2, defining Temp_Run2
4.	Take job#n & draw vector from base to job#n, defining Temp_Runn
(Number of available drivers = n)
5.	There are now n test vectors for the n runs. We now assess the
result of this vector combination
6.	Assign all points to their closest vector (IE perpendicular distance)
7.	Run a TSP algorithm on the group of points assigned to each vector,
to deduce the travel time and kilometres for the optimal destination
sequence (point ordering) for each vector
8.	We now have individual runs defined for each vector, together with
the cost of each. Assess this state, to determine how closely it fits
the optimal state, being the closest aligned proportion for each run
(equal proportions for equal work distribution etc) OR the lowest
fleet cost
9.	We have defined the primary allocation state, but can now commence
some optimisations, to move some allocations to see if a slightly
better fit can be achieved, such as where there is a cost saving if
one job is moved from one vector to another, despite it perhaps being
closest to the initial vector
a.	We store the optimal sequence of each run calculated, so this
effort is not duplicated later. Any TSP routine first checks to see if
there is a pre-calculated result for the job assignment group, to save
doing TSP again
b.	We work to a nominated search depth. Initially we move only ONE job
to another vector, and test to see if there is any saving. Move all
points (once) to another vector, until we have tried all combinations
c.	Increment search depth, now trying to move all combinations of two points
i.	Save best state for each move combination
ii.	For best z combinations, perform thread optimisation
1.	Thread optimisation is where we follow ?good? seams of moves, and
do not attempt to search all move possibilities, but rather sequences
of ?good? suggestions. So we may move three points, and find a much
better solution, so we continue moving points to seek a better
solution, perhaps moving a large number of points in this process,
though not searching exhaustively through all possible combinations.
Stop moving points when there has been no improvement in state for
last q moves ? IE we can continue improving indefinitely, provided
there is improvement every so often
10.	Increment job#n vector, to be drawn from base to n+1
a.	If this vector combination has NOT been assessed previously, run
above routine to assess state
b.	If we have moved this vector right around to all points, we need to
increment Temp_n-1, IE we keep this vector fixed at the last point we
have tried, and commence rotating the next vector. Run above routine
to assess state
11.	If all vector combinations have been tried, we have finished our
assessment. Select the optimal vector combination and job assignments

DEFINE RUN BOUNDARIES
It may be easier to define actual area boundaries, based on workloads,
driving times and distances etc. This allows automatic allocation of
jobs on-the-fly.
1.	Obtain workload history based on location, and map to show busy
areas vs. quiet areas. Define coefficient for workload. An example
would be to plot jobs vs. postcodes
2.	Weight each road segment based on segment length and workload coefficient
3.	Calculate the sum total of all segment values across the entire
road network ? adding distance (average?) & workload values, to
determine the total available fleet workload for the area
4.	Determine the proportionate workload for each staff member. This
may be equal proportions (1:1:1), but a part time staff member may
only work three days per week, so they may receive an area workload of
3/5 of a normal employee
5.	Assign each staff a total ?across the board? capacity, reflecting
the individual workload proportion versus the total available fleet
workload. Momentarily disregard the travel time component at this
point
6.	Perform run cutting routine, which assumes all areas will be worked
proportionately
7.	Consider varying the total workload value to better apportion all
possible segments in one pass ? IE an iterative approach
8.	Define boundaries based on the allocation of all possible jobs to staff as above
9.	Consider minor administrative variations to boundaries, such as
making them snap to existing postcode / suburb boundaries, for ease of
understanding and processing etc (as opposed to using the ragged or
less easily defined boundaries)
10.	Consider home exclusion zone, to prevent problems with staff
members attending to jobs very close to home, and later having
unexpected contact with customers in local shopping areas etc (Not
applicable to sales fleets, but perhaps to RSPCA fleets where
customers may be disgruntled etc)