Dense Routing

Dense Routing refers to a route optimization problem where jobs occur on many or most of the addresses on each street. The number of jobs in such a problem is often extremely large, making it infeasible to optimize via a build without performing a pre-processing step to reduce the number of jobs to be assigned.

The consolidate request can be used for this purpose. The consolidate call takes advantage of the assumption that a driver will service all of the jobs on a street in a single visit, and generates jobs that represent starting at one end of a street and travelling to the other end, servicing each job along the way. This consolidation step can greatly reduce the number of jobs in a problem, which enables RouteCloud to perform optimization tasks.

RouteCloud can use one of two methods to determine if a sequence of jobs on a street are eligible to be consolidated:

  • The consolidate_by_job_restrictions call considers two jobs ineligible to be consolidated if they differ in any of the properties that restrict which routes they can be assigned to
  • The consolidate_by_route_assignments call determines which routes and vehicles could service each job and considers two jobs ineligible to be consolidated if they cannot be serviced by exactly the same set of routes and vehicles.
Note

To run the examples in this tutorial, you will need:

  • A RouteCloud API login. Use your Verizon Connect Enterprise username and password to authenticate with the RouteCloud API. To obtain a username and password, contact Verizon Connect sales.
  • cURL to run the requests. You can download a cURL binary from here.

Consolidating By Job Restrictions

If routes are not able to be provided, a more conservative consolidation can be performed that will avoid consolidating jobs that differ in a way that has the possibility of preventing them from being serviced together.

Request

{
	"jobs": [
		{ "id": "job0", "location": "39.721804,-104.969621", "date": "2020-11-23" },
		{ "id": "job1", "location": "39.721628,-104.969654", "date": "2020-11-24" },
		{ "id": "job2", "location": "39.721434,-104.969673", "date": "2020-11-23", "required_route_attributes": ["hazmat"] },
		{ "id": "job3", "location": "39.721291,-104.969676", "date": "2020-11-24" },
		{ "id": "job4", "location": "39.721157,-104.969701", "date": "2020-11-23" },
		{ "id": "job5", "location": "39.720875,-104.969667", "date": "2020-11-25" },
		{ "id": "job6", "location": "39.720705,-104.969686", "date": "2020-11-24" },
		{ "id": "job7", "location": "39.720519,-104.969636", "date": "2020-11-23" },
		{ "id": "job8", "location": "39.720347,-104.969651", "date": "2020-11-24" },
		{ "id": "job9", "location": "39.720362,-104.969205", "allowed_days_of_week": ["mon", "tue"] },
		{ "id": "job10", "location": "39.720520,-104.969191", "allowed_days_of_week": ["mon", "tue"] },
		{ "id": "job11", "location": "39.720671,-104.969193", "allowed_days_of_week": ["mon", "tue"] },
		{ "id": "job12", "location": "39.720806,-104.969173", "allowed_days_of_week": ["tue", "wed"] },
		{ "id": "job13", "location": "39.721030,-104.969168", "allowed_days_of_week": ["tue", "wed"] },
		{ "id": "job14", "location": "39.721203,-104.969163", "allowed_days_of_week": ["tue", "wed"] },
		{ "id": "job15", "location": "39.721366,-104.969158", "allowed_days_of_week": ["wed", "thu"] },
		{ "id": "job16", "location": "39.721520,-104.969133", "allowed_days_of_week": ["wed", "thu"] },
		{ "id": "job17", "location": "39.721717,-104.969223", "allowed_days_of_week": ["wed", "thu"] }
	],
	"return_request": true
}

consolidate_by_job_restrictions_request.json consolidate request - download it from here. Click here to open it in the UI.

consolidate_by_job_restrictions_request.json specifies eighteen jobs. return_request is set to true in order to be provided with a full problem in the response.

  • All jobs are on the same street in Denver, CO, with the first nine on the west side and the remaining nine on the east side of the road.
  • Jobs job0, job2, job4, and job7 must be completed on November 23.
  • Job job2 must be serviced by a route that has the "hazmat" attribute.
  • Jobs job1, job3, job6, and job8 must be completed on November 24.
  • Job job5 must be completed on November 25.
  • Jobs job9, job10, and job11 can be completed on Monday or Tuesday.
  • Jobs job12, job13, and job14 can be completed on Tuesday or Wednesday.
  • Jobs job15, job16, and job17 can be completed on Wednesday or Thursday.

Response

{
    "jobs": [
        {
            "id": "job0",
            "date": "2020-11-23T00:00:00",
            "location": "39.721804,-104.969621"
        },
        {
            "id": "job2",
            "date": "2020-11-23T00:00:00",
            "location": "39.721434,-104.969673",
            "required_route_attributes": [ "hazmat" ]
        },
        {
            "id": "d316b9f3-1be7-449e-975f-884d06dcaaa9",
            "date": "2020-11-24T00:00:00",
            "custom": {
                "inner_jobs": "['job1','job3','job6','job8']"
            },
            "location": "39.721628,-104.969654",
            "exit_location": "39.720347,-104.969651"
        },
        {
            "id": "b5af75b7-26f0-4442-b9ac-53c08dadbaa6",
            "date": "2020-11-23T00:00:00",
            "custom": {
                "inner_jobs": "['job4','job7']"
            },
            "location": "39.721157,-104.969701",
            "exit_location": "39.720519,-104.969636"
        },
        {
            "id": "job5",
            "date": "2020-11-25T00:00:00",
            "location": "39.720875,-104.969667"
        },
        {
            "id": "f8c3aa33-8642-43b5-9045-4a7b6af9773e",
            "allowed_days_of_week": [ "mon", "tue" ],
            "custom": {
                "inner_jobs": "['job9','job10','job11']"
            },
            "location": "39.720362,-104.969205",
            "exit_location": "39.720671,-104.969193"
        },
        {
            "id": "db1263dd-1309-45d8-a5e4-d697152a7f1b",
            "allowed_days_of_week": [ "tue", "wed" ],
            "custom": {
                "inner_jobs": "['job12','job13','job14']"
            },
            "location": "39.720806,-104.969173",
            "exit_location": "39.721203,-104.969163"
        },
        {
            "id": "8100e3d3-cde3-421c-b728-21eaf513bcec",
            "allowed_days_of_week": [ "wed", "thu" ],
            "custom": {
                "inner_jobs": "['job15','job16','job17']"
            },
            "location": "39.721366,-104.969158",
            "exit_location": "39.721717,-104.969223"
        }
    ],
    "return_request": true
}

Snipped consolidate response - download a full copy from here. Click here to open it in the UI.

Explanation:

  • This call to the consolidate_by_job_restrictions endpoint has reduced the number of jobs in the problem from 18 to 8.
  • Jobs job0 to job8 occur in a row up the west side of the street, so can be completed sequentially.
    • Jobs job0, job2, job4, and job7 must be serviced on November 23, but job2 has an additional requirement of the "hazmat" attribute.
    • As a result, this sequence is split into three parts to ensure that job2 can be serviced in-line with the others, while still being possible to place it on a different route if it is preferable to service the remaining jobs on a route without the necessary attribute.
    • Jobs job1, job3, job6, and job8 must be serviced on November 24 with no other restrictions, so a consolidated job is created representing this sequence.
    • Job job5 is the only job on this side of the road that must serviced on November 25, so it is returned unmodified.
  • Jobs job9 to job17 occur in a row down the east side of the street, so can be completed sequentially.
    • Jobs job9, job10, and job11 can be serviced on a Monday or a Tuesday.
    • Jobs job12, job13, and job14 can be serviced on a Tuesday or a Wednesday.
    • Jobs job15, job16, and job17 can be serviced on a Wednesday or a Thursday.
    • It is not clear until optimization is carried out whether these groups of jobs will be assigned to the same or different routes, so a conservative approach is taken which results in a consolidated job for each group of three jobs.
  • Each consolidated job has a copy of its inner jobs' constraints in order to ensure that it is still assignable to the same set of routes.
  • Each consolidated job has the location of its first inner job as its location and the location of its last inner job as its exit_location. See Routing with Linked Stops.

Consolidating By Route Assignments

If routes are able to be provided, RouteCloud can first determine which jobs can be serviced on which routes, and use this information to more accurately determine which jobs are eligible to be consolidated.

Request

{
	"routes": [
		{
			"id": "route0",
			"location": "39.718005, -104.969531",
			"date": "2020-11-23",
			"start_time": "08:00:00",
			"max_working_time": "09:00:00",
			"route_attributes": ["hazmat"]
		},
		{
			"id": "route1",
			"location": "39.718005, -104.969531",
			"date": "2020-11-24",
			"start_time": "08:00:00",
			"max_working_time": "09:00:00"
		},
		{
			"id": "route2",
			"location": "39.718005, -104.969531",
			"date": "2020-11-25",
			"start_time": "08:00:00",
			"max_working_time": "09:00:00"
		}
	],
	"jobs": [
		{ "id": "job0", "location": "39.721804,-104.969621", "date": "2020-11-23" },
		{ "id": "job1", "location": "39.721628,-104.969654", "date": "2020-11-24" },
		{ "id": "job2", "location": "39.721434,-104.969673", "date": "2020-11-23", "required_route_attributes": ["hazmat"] },
		{ "id": "job3", "location": "39.721291,-104.969676", "date": "2020-11-24" },
		{ "id": "job4", "location": "39.721157,-104.969701", "date": "2020-11-23" },
		{ "id": "job5", "location": "39.720875,-104.969667", "date": "2020-11-25" },
		{ "id": "job6", "location": "39.720705,-104.969686", "date": "2020-11-24" },
		{ "id": "job7", "location": "39.720519,-104.969636", "date": "2020-11-23" },
		{ "id": "job8", "location": "39.720347,-104.969651", "date": "2020-11-24" },
		{ "id": "job9", "location": "39.720362,-104.969205", "allowed_days_of_week": ["mon", "tue"] },
		{ "id": "job10", "location": "39.720520,-104.969191", "allowed_days_of_week": ["mon", "tue"] },
		{ "id": "job11", "location": "39.720671,-104.969193", "allowed_days_of_week": ["mon", "tue"] },
		{ "id": "job12", "location": "39.720806,-104.969173", "allowed_days_of_week": ["tue", "wed"] },
		{ "id": "job13", "location": "39.721030,-104.969168", "allowed_days_of_week": ["tue", "wed"] },
		{ "id": "job14", "location": "39.721203,-104.969163", "allowed_days_of_week": ["tue", "wed"] },
		{ "id": "job15", "location": "39.721366,-104.969158", "allowed_days_of_week": ["wed", "thu"] },
		{ "id": "job16", "location": "39.721520,-104.969133", "allowed_days_of_week": ["wed", "thu"] },
		{ "id": "job17", "location": "39.721717,-104.969223", "allowed_days_of_week": ["wed", "thu"] }
	],
	"return_request": true
}

consolidate_by_route_assignments_request.json consolidate request - download it from here. Click here to open it in the UI.

consolidate_by_route_assignments_request.json specifies the same eighteen jobs as in the previous section, as well as three routes. return_request is set to true in order to be provided with a full problem in the response.

  • Jobs job0, job2, job4, and job7 must be completed on November 23 so must be placed on route route0.
  • Route route0 has the "hazmat" attribute, so this additional restriction on job job2 has no effect on which routes it can be placed on.
  • Jobs job1, job3, job6, and job8 must be completed on November 24 so must be placed on route route1.
  • Job job5 must be completed on November 25 so much be placed on route route2.
  • Jobs job9, job10, and job11 can be completed on Monday or Tuesday so can be placed on route0 or route1.
  • Jobs job12, job13, and job14 can be completed on Tuesday or Wednesday so can be placed on route1 or route2.
  • Jobs job15, job16, and job17 can be completed on Wednesday or Thursday so must be placed on route2.

Response

{
    "jobs": [
        {
            "id": "6bc68cae-595c-4aea-8779-1056228f2a8b",
            "date": "2020-11-23T00:00:00",
            "custom": {
                "inner_jobs": "['job0','job2','job4','job7']"
            },
            "location": "39.721804,-104.969621",
            "exit_location": "39.720519,-104.969636",
            "required_route_attributes": [ "hazmat" ]
        },
        {
            "id": "c241b030-6d95-452b-b630-86bb5119c041",
            "date": "2020-11-24T00:00:00",
            "custom": {
                "inner_jobs": "['job1','job3','job6','job8']"
            },
            "location": "39.721628,-104.969654",
            "exit_location": "39.720347,-104.969651"
        },
        {
            "id": "job5",
            "date": "2020-11-25T00:00:00",
            "location": "39.720875,-104.969667"
        },
        {
            "id": "b19c7951-d8f1-405c-9b43-d9c445a6ef4d",
            "allowed_days_of_week": [ "mon", "tue" ],
            "custom": {
                "inner_jobs": "['job9','job10','job11']"
            },
            "location": "39.720362,-104.969205",
            "exit_location": "39.720671,-104.969193"
        },
        {
            "id": "ead01c7b-6947-4cc0-a3d9-359c11b3729a",
            "allowed_days_of_week": [ "tue", "wed" ],
            "custom": {
                "inner_jobs": "['job12','job13','job14']"
            },
            "location": "39.720806,-104.969173",
            "exit_location": "39.721203,-104.969163"
        },
        {
            "id": "a58ed525-7e0f-4f17-ba37-d1b0e51ed2c2",
            "allowed_days_of_week": [ "wed", "thu" ],
            "custom": {
                "inner_jobs": "['job15','job16','job17']"
            },
            "location": "39.721366,-104.969158",
            "exit_location": "39.721717,-104.969223"
        }
    ],
    "routes": [
        {
            "id": "route0",
            "date": "2020-11-23T00:00:00",
            "start_time": "08:00:00",
            "max_working_time": "09:00:00",
            "location": "39.718005,-104.969531",
            "route_attributes": [
                "hazmat"
            ]
        },
        {
            "id": "route1",
            "date": "2020-11-24T00:00:00",
            "start_time": "08:00:00",
            "max_working_time": "09:00:00",
            "location": "39.718005,-104.969531"
        },
        {
            "id": "route2",
            "date": "2020-11-25T00:00:00",
            "start_time": "08:00:00",
            "max_working_time": "09:00:00",
            "location": "39.718005,-104.969531"
        }
    ],
    "return_request": true
}

Snipped consolidate response - download a full copy from here. Click here to open it in the UI.

Explanation:

  • This call to the consolidate_by_route_assignments endpoint has reduced the number of jobs in the problem from 18 to 6.
  • Jobs job0 to job8 occur in a row up the west side of the street, so can be completed sequentially.
    • Jobs job0, job2, job4, and job7 must be placed on route0, so a consolidated job is created representing this sequence.
    • Jobs job1, job3, job6, and job8 must be placed on route1, so a consolidated job is created representing this sequence.
    • Job job5 is the only job on this side of the road that must placed on route2, so it is returned unmodified.
  • Jobs job9 to job17 occur in a row down the east side of the street, so can be completed sequentially.
    • Jobs job9, job10, and job11 can be placed on route0 or route1.
    • Jobs job12, job13, and job14 can be placed on route1 or route2.
    • Jobs job15, job16, and job17 must be placed on route2.
    • It is not clear until optimization is carried out whether these groups of jobs will be assigned to the same or different routes, so a conservative approach is taken which results in a consolidated job for each group of three jobs.
  • Each consolidated job has a copy of its inner jobs' constraints in order to ensure that it is still assignable to the same set of routes.
  • Each consolidated job has the location of its first inner job as its location and the location of its last inner job as its exit_location. See Routing with Linked Stops.

See Also