I am doing a route optimisation for delivery vehicles and failing dismally. Please see problem statement below. My current solution uses FindShortestTour, but this does not have defined start and end points. 

Data is received from the calling application in the following format: {"Unique Identifier used by server", Original order, Task locked, Latitude, Longitude}

The first point will always have the unique identifier "00000000-0000-0000-0000-000000000000" and represents the depot. 
This point will always have an order of 1 and always be locked.

A number of tasks may be locked in their given order at the beginning of the list. 
The Task locked is a boolean represented by 1 - locked, 0 - unlocked.
These locked tasks are not included in the optimisation as they are fixed in their given order at the beginning of the scheduled.

The route is to be optimised finding the shortest path starting at the last locked point and ending back at the depot, traversing all other unlocked points. 
Depot is always locked and will be used if there are no other locked tasks. 

The output is to be in the following format: {"Unique Identifier used by server", Original order, Distance to Next Task in km} and is to be arranged in the optimal order. 
The order will always start with the depot the traverse locked Tasks in their given order. 
This will be followed by unlocked tasks optimised from the last locked to the depot. 
This list will not contain the final depot point as the distance returned is the distance to next task.
i.e. The last ordered task distance will be the distance from itself to the depot.

The calculation needs to be able to handle the optimisation of 30 points in under a minute as accurately as possible.

  

   

    input = {{"00000000-0000-0000-0000-000000000000", 1., 
        1., -26.17132739, 
        28.21375807}, {"817463b3-e330-4405-9008-e21821e6c121", 2., 
        1., -26.2055333333333, 
        28.420565}, {"36418378-a9ef-49d7-be5a-3a54264a8479", 3., 
        0., -25.99202013, 
        27.53309061}, {"49595197-11e5-463a-8f7b-6cd294c33f43", 4., 
        0., -26.14895194, 
        27.92271447}, {"83fd029b-0313-4519-a785-ff7b9843c85c", 5., 
        0., -26.169355, 
        28.2079083333333}, {"612bf08a-1679-4feb-8fee-d12deb49803a", 6., 
        0., -25.6755766666667, 
        28.0820533333333}, {"382f1997-5efe-42c1-99f5-bcb8da30e1c8", 7., 
        0., -26.8742866666667, 
        28.25047}, {"883d68f2-b50f-48ca-b065-febfc6ea9546", 8., 
        0., -26.0938733333333, 
        28.1937966666667}, {"1bf089bf-acae-4a41-8c4b-e120cef8a148", 9., 
        0., -25.9877716666667, 
        28.0691433333333}, {"6958e90b-d42a-4c13-b6ec-78bbdd301aba", 10., 
        0., -25.7661166666667, 
        28.2811033333333}, {"2f2c5d25-c1de-449e-b779-dd95699d83ed", 11., 
        0., -26.0474216666667, 
        28.0060766666667}, {"a11feb01-f067-49aa-b99d-50879229c423", 12., 
        0., -25.7949916666667, 
        28.29928}, {"729b8bfb-029a-483a-814a-1575a6fe47bc", 13., 
        0., -26.0258616666667, 
        28.0692033333333}, {"732771dd-55fd-4074-a097-2665686f67d8", 14., 
        0., -26.772045, 
        28.49977}, {"0690914d-ba34-4086-b5ae-feda7ed6d22b", 15., 
        0., -26.044905, 
        28.0346666666667}, {"5de23f0e-9a05-40af-8e1e-f887d5a06452", 16., 
        0., -26.4070083333333, 
        28.138515}, {"3e95a2ac-9985-4753-a4cc-5372ca44ed12", 17., 
        0., -25.64392423, 
        28.13148167}, {"d2e0bce2-8061-4b57-b983-aa409c1532fe", 18., 
        0., -26.42138814, 
        28.1074221}, {"0259d54a-0782-4ac8-a5f6-42af6e3edbc3", 19., 
        0., -25.78637, 28.28066}, {"f686b23a-de85-4004-ae70-8d2703336b5d",
         20., 0., -26.043795, 
        28.1197816666667}, {"e8bca7d4-69ad-4477-8791-9daedbc563c9", 21., 
        0., -26.2624883333333, 28.17859}};
    
    
    outputReturned = {{"00000000-0000-0000-0000-000000000000", 1., 
       21.020}, {"817463b3-e330-4405-9008-e21821e6c121", 2., 
       26.772045}, {"732771dd-55fd-4074-a097-2665686f67d8", 14., 
       63.26}, {"382f1997-5efe-42c1-99f5-bcb8da30e1c8", 7., 
       27.24}, ..., {"83fd029b-0313-4519-a785-ff7b9843c85c", 5., 0.62}}

   
Current poor solution here:
https://dl.dropbox.com/u/9666857/Schedule.m

**Edit**
The requirement boils down to a traveling salesman path problem.

I have a fixed start and end point with a list of intermediate points which need to be visited exactly once in an optimal order.

I have a working solution [here][1]


  [1]: https://dl.dropbox.com/u/9666857/Working%20Solution.nb