Charlie Alfred’s Weblog

Complexity-Driven #4

Introduction

In https://charliealfred.wordpress.com/complexity-driven-3, I described a systems development problem, in the transportation and logistics domain.  The problem is to architect an automted system to help improve local area pickup and/or delivery operations.  We will use this example to illustrate the principles of complexity-driven development, described in https://charliealfred.wordpress.com/complexity-driven-2.

The transportation industry is heavily constrained by real-world forces, such as the time to drive between two locations, the length of a driver’s work day, and the capacity of the vehicle.  It is a highly competitive industry, driven by operational improvements that increase efficiency.

Transportation logistics are a problem in combinatorial optimization. (http://en.wikipedia.org/wiki/Traveling_salesman_problem.  There are a seemingly endless number of possible solutions, and brute force optimization is infeasible.

The main wrinkle is that in this exersize we are considering three different contexts:

·       Less Than Truckload (LTL)  Roadway, Yellow Freight

·       Overnignt Parcel – UPS, FedEx, DHL

·       Private Fleet – Bottled Water, Restaurant, Uniform Service, etc.

In theory, there are enough similarities between these contexts for us to strongly consider designing a common solution.  However, there appear to be some significant differences, as well.

Approach

We attack the local-area pickup and delivery problem with these steps:

1.     Look for complexities that originate in the deployment and technology areas.  Ordinarily, we would also include the work management area, but since we are not working with an actual development organization, we would have to fabricate these concerns.

2.    Separate these complexities into groups that represent different concerns in the solution space.  For example, complexities in communicating with on-road drivers are fundamentally different than those of estimating travel time and distance.  The need for subject matter experts to classify and assess these complexities is a compelling reason to do this step.

3.    Further separate the groups of complexities into those which are shared, and those which are contextual.  In this problem, we consider three different deployment contexts: LTL, Parcel, and Private Fleet.  While their goals and challenges are similar, they are not identical.  Some capabilities that are essential for LTL are not useful for Private Fleet, and some that are important for Private Fleet are not for the other two.

4.   Prioritize the significance of each group of complexities from each of the following perspectives:

a.    Importance to each Deployment Context

o      LTL Context

o      Overnight Parcel Context

o      Private Fleet Context

b.    Difficulty

o      How hard will it be to address this challenge well?  What are the consequences of coming up short?

o      Are there many likely solutions, or just a few?  What are the consequences if the best approach cannot be

o      Can solutions be purchased or must they be developed?  What are the consequences for skills. training and/or development (design, code, debug, test)?

c.     Pervasiveness

o      how much does a solution to this challenge constrain or enable potential solutions to other challenges?

o      How interdependent or isolated is this challenge from the rest of the system?

5.   Contrast the per-context importance priorities from the previous task.  This assessment will help to clarify:

a.    How consistent are the most important challenges?  The point where pre-context priorities diverge is a good initial inidcator of the scope of a common framework.

b.    Are there challenges which can be encapsulated?  Services have a common interface, with a choice of implementations.  Non-pervasive challenges make good services. 

6.   Decide on the approach to be taken for product line architecture.  A few possibilities include:

a.   Design and build specific solutions for each context, using some common assets in each solution.

b.   Design a single solution with sufficient flexibility to address all deployment contexts.

c.    Exclude some context(s) in order to focus other the others.

d.   Define a platform, or framework that solves the common aspects of the problem.  Solutions for each context-specific problem can be built on the platform/framework.

7.   Based on the result of tasks 4 and 6, put the architecture challenges in priority order.  Now that we have accounted for cross-context differences in challenges, we can identify the rough sequence in which we will address architecture challenges.

8.  Iterate through the prioritized architecture challenges and formulate approaches.  When comparing approaches, consider how well each approach addresses its target challenge, and what tradeoffs or risks it imposes on lower priority challenges.

Deployment and Technology Complexities

Since https://charliealfred.wordpress.com/complexity-driven-3 contains a reasonably detailed description of the problem, we will not repeat that discussion here.

The following table summarized the primary complexities discovered in the deployment context.   The one that follows it summarized the complexities from the technology domain.

Category

Deployment-Context Complexity

Function

How to determine which stops to assign to each driver and which sequence to visit them in

Loading the right shipments onto the right vehicles in effective locations

Disptaching work to on-road drivers

Dispatchers are mostly high-school educated, work long hours, and time for training is rare

Information

How do I match bills of lading with customers?

Acquire updated status info for on-road drivers

Where are my pickups today?  What are they?

Control

Acquire exception information that affects the process of loading outbound delivery vehicles

Notification to dispatcher of shipment load status

Notification to dock of changes in schedule

Coordination between multiple dispatchers communcating with on-road drivers

Algorithmic

Need smooth transition from static to dynamic approach to stop assignment and sequencing

Contextual Variation

Repeat vs. One-time Customers

Account for stop x customer x vehicle constraints

Making large pickups first so that freight doesn’t need to be rehandled

Single vs. Multi-day routing and scheduling

Street-level vs. Area-level travel

Evolution

Wireless radio communication is a constraint to growth

 

Category

Technology Complexity

Functional

How to make stops and routes visible, displaying the proper level of street detail, while providing “at a glance” information

How to override route and sequencing decisions

Information

Electronic download of today’s shipments, in the absense of standard data formats and protocols

Efficiently manage queries to match delivery information with customer names and street addresses

Aquire driver on-road status info reliably and inexpensively

Acquire exception information that affects the process of loading outbound delivery vehicles

Large quanties of street data (relational query)

Large quantities of travel info (network access)

Record and use “synonyms” for customer names and street addresses

Control

Mechanics of communicating with on-road drivers

Coordinating actions of multiple dispatchers

Coordinating dispatcher and dock supervisor

Algorithmic

Driver and stop-based routing/scheduling problems have non-polynomial complexity

Travel estimation over a street network also has (non-polinomial) complexity

Several travel time estimates must be made and compared for each routing/scheduling decision.

Scheduling around service window constraints

Need to support different approaches: static (zone), dynamic, and incremental

Modeling travel exceptions, such as: rush hour, construction, and accidents

Contextual Variation

Support for Street Level vs Area Level Travel estimation

Importance of Travel Model detail increases as stop density increases.

Need for on-road routing, scheduling, dispatch?

Account for stop x customer x vehicle constraints

Evolution

Geocoding Database availability (street addresses to coordinates) from 3rd party suppliers

Cellular telephones with GPS Receivers to enable driver location and dispatcher-driver communication

 

Group and Prioritize Complexities

The following table shows the results of completing tasks 2-4.  Specifically, what we did here was to:

o      Combine the complexities discovered in the deployment contexts and the technology space, and eliminate redundant items.

o      Organize the remaining complexities into groups that represent solution-space concerns

o      Separate the complexities that have universal concern into different sub-groups from those which are context-sensitive.  The context-sensitive rows have the letter C as part of their ID.

o      From the perspective of each context, rank the the relative importance of the 15 sub-groups of complexities.

o      Assess the level of pervasiveness and design difficulty for each sub-group of challenges.

Here, all rankings are ordinal values ranging from 15 (high) to 1 (low).  One can also use a set of weighted values that sum to a specific total.

ID

Complexity Group

LTL

Parcl

PF

Diff

Per

1

Figuring out the amount of work and where it  is located?

8

8

8

10

3

Electronic download of today’s shipments, in the absense of standard data formats and protocols

Geocoding Database availability (street addresses to coordinates) from 3rd party suppliers

1C

Handling large volumes of new delivery customers

11

3

4

7

2

How do I match bills of lading with customers?

Efficiently manage queries to match delivery information with customer names and street addresses

Record “synonyms” for customer names and street addresses

2

Coordinating AM routing and scheduling with dock operation (loading deliveries)

10

7

7

5

8

Notification to dispatcher of shipment load status

Notification to dock of changes in schedule

2C

Coordinating AM routing and scheduling with dock operation (loading deliveries)

9

6

6

4

7

Loading the right shipments onto the right vehicles in effective locations

Acquire exception information that affects the process of loading outbound delivery vehicles

3

Automated scheduling

13

15

12

15

12

How to determine which stops to assign to each driver and which sequence to visit them in

Driver and stop-based routing/scheduling problems have non-polynomial complexity

Scheduling around service window constraints

3C1

Managing Large Shipments

7

1

5

1

13

Accounting for stop x customer x vehicle constraints

Making large pickups first so that freight doesn’t need to be rehandled

3C2

Static vs. Dynamic Routing and Scheduling

14

14

11

11

15

Need to support different approaches: static (zone), dynamic, and incremental

Need smooth transition from static to dynamic approach

3C3

Scope of Routing and Scheduling Activities

1

2

15

13

10

Single vs. Multi-day routing and scheduling

4

Travel time and distance estimation

5

11

10

14

5

Several travel time estimates must be made and compared for each routing and scheduling decision.

Modeling travel exceptions: rush hour, construction, and accidents

4C

Street-Level Travel Estimation

3

10

14

12

4

Travel estimation over a street network also has (non-polinomial) complexity

Several travel time estimates must be made and compared for each routing and scheduling decision.

Support for Street-level vs. Area-level travel

Importance of Travel Model detail increases as stop density increases.

5

Coordination Between Dispatchers and On-Road Drivers

12

9

3

6

11

Aquire driver on-road status info reliably and inexpensively

Mechanics of communicating with on-road drivers

Wireless radio communications are a constraint to growth

Cellular telephones with GPS Receivers to enable driver location and dispatcher-driver communication

5C

Pickup stop forecasting

6

5

1

3

1

Where are my pickups today?  What are they?

6

Dispatcher User Interface (Usability)

15

13

13

8

9

Dispatchers are mostly high-school educated, work long hours, and time for training is rare

How to make stops and routes visible, displaying the proper level of street detail, while providing “at a glance” information

How to override route and sequencing decisions

7

Coordination between multiple dispatchers

2

4

2

2

6

8

Data Management

4

12

9

9

14

Large quanties of street data (relational query)

Large quantities of travel info (network access)

 

Context-Sensitive Importance Rankings

So far, we have identified the main complexities from the deployment environment and technology areas, consolidated them and organized them into context-sensitive complexity groups.  Next, we ranked the relative imporantance of each complexity group from the perspective of each context (LTL, Overnight Parcel, and Private Fleet).

The strongest indication that a product-line framework or platform is a viable solution is for the most important complexity groups to be consistent across contexts.

For this example, we will look at each of the capability groups that are ranked between 10-15 for any context.  The columns in this table are:

LTL             Importance for the Less Than Truckload context

Parcel          Importance for the Overnight Parcel context

PF               Importance for the Private Fleet context

Delta           Difference from highest context rank to lowest

Max             Highest ranking from any context

Median       Median ranking from all contexts

The columns are sorted in descending order, according to the median importance (the tiebreakers are Max and Mean, in that order).  The highlighted cells identify complexity groups with a Delta over 7 (i.e. over 50% gap in perceived importance).  These capability groups represent the biggest risks for a product line architecture.

ID

Complexity  Group

LTL

Parcel

PF

Delta

Max

Median

3C2

Static vs. Dynamic Routing and Scheduling

14

14

11

3

14

14

6

Dispatcher User Interface (Usability)

15

13

13

2

15

13

3

Automated scheduling

13

15

12

3

15

13

4C

Street-Level Travel Estimation

3

10

14

11

14

10

4

Travel time and distance estimation

5

11

10

6

11

10

5

Coordination Between Dispatchers and On-Road Drivers

12

9

3

9

12

9

8

Data Management

4

12

9

8

12

9

2

Coordinating AM routing and scheduling with dock operation (loading deliveries)

10

7

7

3

10

7

1C

Handling large volumes of new delivery customers

11

3

4

8

11

4

3C3

Scope of Routing and Scheduling Activities

1

2

15

14

15

2

Assess Product-Line Architecture Approach

The first major architectural decisions we face is whether a product-line architecture approach is appropriate.  Consider that:

1.     The importance of this decision is extremely high:

a.    The cost to independently architect, develop, and support three distinct routing and scheduling products will be very expensive (if not prohibitive).

b.    By contrast, focusing exclusively on one segment reduces development cost, but also limits market potential.

2.    The pervasiveness of this decision is “off the charts” high.  Most, if not all, major technical decisions will be affected by the span of contexts served.  In addition, as Clements and Northrup observe, a product line approach also has significant organizational and managerial impact.

3.    The difficulty of a product line approach depends on how well aligned the contexts are.  If the contexts are pretty closely aligned, then the difficulty might only be somewhat higher than solving any one of the problems.   One way to look at this difficulty is thinking about making a spare in bowling.  When two pins are close together (4, 7), it is easier than when they are spread apart (7, 10).

The good news in the previous table is that there is very good alignment among the top three complexity groups.  These groups are the three most important for LTL and Parcel, and are 3 of the top 5 for Private Fleet.  The bad news, however, is that 5 out of 10 the complexity groups have Delta values above 7 (where 7 represents 50% of the importance range from 1-15).  These cells are highlighted in gold in the above table.

The large Delta values may, or may not, spell trouble for a product line architecture:

o      It may be possible to drop a context from the product line architecture and build a framework for the others.

o      If these complexities are isolated (low pervasiveness), then it may be possble to hide the differences behind a stable interface.

o      Finally, for complexities with small Deltas, and low pervasiveness, it may be possible to reuse them as isolated services.

So, let’s insert the Difficulty and Pervasiveness rankings in our table:

ID

Complexity Group

LTL

Parcel

PF

Delta

Diff

Per

3C2

Static vs. Dynamic Routing and Scheduling

14

14

11

3

11

15

6

Dispatcher User Interface (Usability)

15

13

13

2

8

9

3

Automated scheduling

13

15

12

3

15

12

4C

Street-Level Travel Estimation

3

10

14

11

12

4

4

Travel time and distance estimation

5

11

10

6

14

5

5

Coordination Between Dispatchers and On-Road Drivers

12

9

3

9

6

11

8

Data Management

4

12

9

8

9

14

2

Coordinating AM routing and scheduling with dock operation (loading deliveries)

10

7

7

3

5

8

1C

Handling large volumes of new delivery customers

11

3

4

8

7

2

3C3

Scope of Routing and Scheduling Activities

1

2

15

14

13

10

This table highlights some interesting findings:

o      In two rows with large importance deltas, it seems plausible to encapsulate the capabilities behind an internal interface (4c) or configure the user interface (1c) into or out of the product.  In the case of travel estimation, since difficulty is high, care must be taken to avoid unintended side-effects of a common approach.

o      In two (3C3 and 5) of the remaining three rows, the Private Fleet context is the cause of the large deltas.  The delta between LTL and Overnight Parcel is 3 and 1 respectively.

o      The remaining row is Data Management.  The large delta between LTL and Overnight Parcel is driven by:

·       Significant differences in the number of customers

·       Need for extensive geocoding data to translate delivery street addresses into map coordinates.

·       Need for detailed street-level travel detail (e.g. MPH, turn restrictions, one-way, difficult to cross streets, etc.)

Decide on Product-Line Architecture Strategy

In the prior step, we learning two things.  First, there are significant differences between the buisiness requirements of Private Fleet and the two other contexts.  Second, 3 of 5 strong contextual differences in capability groups are difficult to isolate.  As a consequence, we will rule out the option of a product line framework spanning all three contexts.

This leaves us with two other strategies:

·       Pursue Product Line framework for LTL and Overnight Parcel

·       Design reusable, modular services that can be configured for different contexts.

The limited product line strategy offers three sub-options:

·       Develop and release LTL and Overnight products in parallel

·       Initial deployment in Overnight Parcel, LTL second

·       Initial deployment in LTL, Overnight Parcel second

The reusable, modular services option is largely independent of the product line option.  The configurable modules include:

·       Travel estimation

·       Automated scheduling

·       Graphical UI

·       Customer and Street Address Matching

·       Dispatcher-Dock Coordination

·       Dispatcher-Driver Communication/Coordination

In a real world problem, the product line framework decision would be driven by several factors, including: sales opportunities, competition, development effort, time to market considerations, and risk assessment.  For the purposes of this exercise, we’ll reach the following conclusions:

·       Time to market considerations and resource constraints preclude parallel development of LTL and Overnight Parcel products running on a common framework.

·       The sales and competitive situations in the LTL context are more favorable.  The risk in the Overnight Parcel context is that the large vendors will prefer to develop a custom in-house solution over buying a product not yet proven in the field.

·       We will design for each of the reusable module opportunities, unless we reach a point where cross-context constraints make a module infeasible.  At this time, travel estimation and automated scheduling appear to have the most risk.

Transform Capability Groups into Challenges

At this point, we have an established product strategy direction, with respect to product line framework and reusable components.  The next step is to reassess our capability groups in light of these decisions, and identify specific challenges that the architecture must address.

The following table revisits the complexity groups defined earlier, but re-examines them through the lens of an LTL/Overnight Parcel product family.  Weighting factors are applied to each factor that represent:

o      perceived business opportunity for each customer context and

o      potential consequence to not overcome the technical obstacles.

ID

Capability Group and Challenge

LTL

Parcel

Diff

Per

Imp

 

Weighting Factor

25%

20%

25%

30%

100%

3

Automated scheduling

13

15

15

12

13.6

3C2

Static vs. Dynamic Routing and Scheduling

14

14

11

15

13.6

6

Dispatcher User Interface (Usability)

15

13

8

9

11.1

8

Data Management

4

12

9

14

9.9

5

Coordination Between Dispatchers and On-Road Drivers

12

9

6

11

9.6

4

Travel time and distance estimation

5

11

14

5

8.5

2

Coordinating AM routing and scheduling with dock operation (loading deliveries)

10

7

5

8

7.6

1

Figuring out the amount of work and where it  is located?

8

8

10

3

7.0

4C

Street-Level Travel Estimation

3

10

12

4

7.0

The complexity groups have been assessed according to their perceived impact (objective) while the weighting factors represent the importance to the development sponsor (subjective).   As a result, the weighting factors transform the complexity groups into challenges. 

Choose Architecture Approaches to Address Key Challenges

Roy Fielding was a lead architect for the World Wide Web, co-founder of the Apache Software Foundation, and the creator of REST Web Services.  His PhD thesis: http://www.ics.uci.edu/~fielding/pubs/dissertation/fielding_dissertation.pdf  asserts that architecture can be defined by a sequence of styles, where each style is a pattern or a set of related decisions.  For example, some of the key architectural styles for the World Wide Web are:

o      Client-Server – browsers issuing requests to Web Servers

o      Stateless Server – Servers do not hold client-specific state

o      Cache – Rules for how clients and proxy servers cache content

o      Uniform Interface – URI’s and HEAD/GET/PUT/POST etc. cmds

o      Layered System – component visibility limited to next layer

o      Code on Demand – code can be downloaded to client on request

Fielding’s thesis is a very important contribution to the field of software architecture.  It allows us to see how each architectural style (approach) exists to address a certain problem (or set of problems), and how each decision in a style constrains downstream decisions.  In particular, a downstream decision complies with the architecture if it conforms to the architectural constraints imposed by upstream decisions.  For example, Fielding points out that:

o      HTTP 1.1 Cookies violate the Stateless Server constraints.

o      SOAP Web Services violate the Uniform Interface constraints.

What Fielding’s PhD thesis does not specify is how an architect should choose the most effective sequence of architecture approaches.  The selection of the Client-Server style seems intuitively obvious.  However, the implicit choice of Stateless Server is not as apparent.

Fielding’s rationale is that the World Wide Web has massive scalability requirements, and cannot achieve these unless servers keep no client state.  However, it is not clear what other challenges were considered for second most significant.  How the tradeoff between serving large volumes of documents by hyperlink reference and the need to process large volumes of online purchase transactions perceived?

The approach described in this article seeks to address this question. A prioritized set of challenges, such as the one in the previous section, provides a roadmap for the architecture approaches that must be defined.  Not only does it provide a roadmap, but in the style of Hansel and Gretel, it provides a tangible, visible, traceable cookie-crumb trail, that allows managers, customers,  and system developers to understand the rationale for important decisions.

The rest of this article will formulate architecture approaches for the most important few architecture challenges.  Due to space and time constraints, I will not attempt to describe a full set of architecture decisions for this problem.  Hopefully, the discussion of the complexities and challenges, the prioritization process, and the initial set of examples will be sufficient to make the rest of the process clear.

Automated Scheduling and Static vs. Dynamic Routing/Scheduling

These two challenges are similar enough, both in scope and complexity that they can be taken together.   The two most important architecture decisions for these challenges are:

o      to make scheduling a service, allowing it to be replaced

o      to make scheduling a configurable service, supporting externally defined algorithm plug-ins.

These two decisions allow the rest of the system to treat the scheduling capability as a black box.  This also allows the specifics of the scheduling implementation to be customized to the context (e.g. LTL vs. Parcel).  It also permits certain components to be reused in a Private Fleet product.

In order to make scheduling a configurable service, we must identify its pluggable components.  In this case, we specify that the scheduler runs a set of Heuristics, governed by a state machine.   Each Heuristic occupies a state, and the state machine’s events and transitions determines the flow of control during a scheduling run.

We also must specify the service interface, specifically:

o      Input:

o      A list of stops to be scheduled, where each stop must have:

§       A location (longitude/latitude coordinates)

§       Its size (e.g. weight, cube, # loose pieces, # pallets)

§       Service window constraints

§       Customer constraints like dock, floor, elevator, etc.

o      A list of pre-determined driver routes, with vehicle type

o      A limit on the number of new drivers that can be added

o      A set of pre-determined stop/route constraints:

§       Stops that are fixed to a particular vehicle location

§       Stops fixed to a driver route (any vehicle location)

§       Stops assigned to a driver route, but can be removed

§       Stops that are not assigned to any driver route

o      Configurable Items:  Heuristics that the Scheduler can run

o      State Machine – guides when Scheduler runs Heuristics

o      Assignment – determine candidate driver routes for stops

o      Router – select stops for each route and sequence

o      Scheduler – identify and fix violations in driver routes

o      Completer – identify which driver routes are complete

o      Required Support Services (i.e. Scheduler service depends on):

o      Estimate travel time and distance between two locations, given a time of day.

o      Estimate time to service a stop, given the data listed above under the Input bullet.

o      Verify the feasibility of a driver’s route (vehicle capacity, service windows, length of driver work day, etc.)

o      Determine if one stop can follow another in the route.  LTL might enforce delivery before pickup or load location.

o      Output:

o      A list of driver routes, each with a list of stops in sequence, where all driver routes pass the feasibility tests

o      A list of stops that could not be assigned to a driver route

The core value proposition of this system is based on these premises:

o      A set of stops can be assigned to drivers and put into an effective sequence in just a few minutes for large, complex workloads.

o      The stop assignments and sequences are realistic:

o      The shipments are consistent with the vehicle’s constraints,

o      Driver arrival and departure time from each stop satisfies customer service window constraints.

o      The time needed to complete the work fits within the bounds of a driver’s workday.

o      Scheduling is an N-P complete problem, meaning that an optimal solution is not feasible.  Fortunately, an optimal solution is not required, just one that leads to operational improvements.

o      For 500 stops, accurate travel estimates (+/- 2%, or 1 minute, whichever is more) must be made for about 30% of the number of combinations (7,500) in under a minute (150/second).

o      The cost to completed the plan produced by the automated system is at least 10% better than a human dispatcher could do in 5 times as much clock time.

o      There is an effective transition from what the carrier does today to a solution that automates the scheduling decisions.

Of the three heuristics, Assignment is by far the most sensitive to:

o      The current scheduling procedures used by prospective carriers:

o      Geographic areas mapped to “zones” in driver vehicles

o      The context in which scheduling occurs:

o      In the AM, before any shipments are loaded onto vehicles

o      In the AM, after some shipments have been loaded

o      After drivers have left the terminal and are on road

o      When dispatchers have manually assigned certain stops to specific drivers

The Assignment algorithm needs to work within a variety of assignment constraints, ranging from unconstrained, to some stops assigned, to most or all stops assigned.  Furthermore, these constraints can vary between drivers (e.g. some have all stops assigned, others have some, and the rest have none).

The main responsibilities of the Assignment heuristic are:

o      Verify that the total cube and weight of shipments is acceptable

o      Estimate the total “at stop” time for each driver route

o      Quickly estimate the approximate travel time of a set of stops based on the size of the service area and its distance from the hub

o      Estimate the number of additional drivers that will be needed to handle the workload, and determine where these drivers provide the most benefit (e.g. areas with many stops but few drivers)

o      Identify the 4-5 closest drivers for each stop, based on the travel time to the closest assigned stop (or to an anchor stop, if none).  Rank these candidate assignments by increasing travel time.

The Routing heuristic works on a per route basis, called a Routing Task.  Each task can work serially (one route at a time), or in parallel (in several concurrent threads).

o      Each Routing Task selects stops for which its route is the best candidate and considering the tradeoff with the next best route.

o      Each Routing Task stops selecting work when it estimates that it has reached vehicle capacity and driver work day constraints.

o      Routing Tasks determine the sequence of stops, based on:

o      Frieght constraints, either actual shipment loading position, or zone load assignment.

o      Seeking to handle stops that are furthest from the hub and closest to the current stop.  See the diagram below.

 

 

o      After a Routing Task has acquired a set of stops for a driver, and sequenced them into an initial route, it tries to improve the sequence by examining stop pairs and swapping the sequence (possibly reversing the order of the intervening stops).

 routing-algorithms3

The Scheduling heuristic also works on a per route basis, called a Scheduling Task.  It works after all Routing Tasks have completed.  The Scheduling Task simulates a driver route, calculating arrival and departure time from each stop, and computing cumulative shipment weight and cube (w.r.t. vehicle capacity).

When problems are detected, the Scheduling heuristic tries to correct them.  Service window constraint violations may be corrected by changing the stops sequence.  When this is not possible, the stop with the violation may need to be removed from the driver’s route.  Vehicle capacity problems and driver workday violations always require selecting one or more stops to remove from the driver route.  These removals must obey the stop assignment constraints.

Travel time and distance estimation

Whoa!  What is this challenge doing here?  On the prioritized list, it was only ranked 6th.  Is this a matter of “architect’s perogative”, where the architect ignores the challenge prioritization and pick the challenges s/he wants to work on?  This is an interesting premise, but false.

What happened is the approach to address the first (scheduling) challenge created new constraints that increased the priority of the travel time and distance challenge.  In particular, the approach to the scheduling challenge requires about 150 travel estimates/second.  This derived requirement escalated the priority of the travel time/distance challenge and bumped it ahead of the others.

Just like the scheduler, the travel model also needs to be defined as a service.  This is neither a coincidence, nor a stylistic preference.  The driver here is that the Overnight Parcel context has different travel model requirements than LTL.  Specifically, for Overnight Parcel, the stop density is higher and more stops are in downtown areas.

In addition to enabling context-specific implementations for LTL and Overnight Parcel, defining the travel model as a service increases the likelihood of reusing one of the travel model service providers for Private Fleet (or future) contexts.

Fortunately, the travel model interface is stable across contexts:

o      Input:

o      The departure time from the from stop

o      Street address and latitude/longitude of the from stop

o      Street address and latitude/longitude of the to stop

o      Dependent Services:  None

o      Configurable Items:

o      Accuracy / Response Time tradeoff

o      Option to describe travel route

o      Output:

o      Travel time, in minutes

o      Travel distance, in miles or kilometers

o      Travel route description, if chosen.

There are a few different travel model designs that could be used to implement this service contract:

Model Type

Approach

Area-based

§        Define areas with consistent travel patterns.

§        Use road densities to estimate travel distance as a function of straight-line distance.

§       Estimate speed by time of day, using area type and density of traffic stops (lights, signs, school zones)

Area-based with highways

§       Define network of local, state, and interstate highways with actual distance between exits/intersections

§       Estimate travel speed on each segment, in each direction, based on AM rush hour, PM rush hour, and other.

§        Use area-based model for surface streets

Street-level

§       Define network with full street detail, including restrictions (one way, turn constraints, and vehicle limitations)

§       Estimate travel speed on each segment, in each direction, based on AM rush hour, PM rush hour, and other.

Hybrid

§        Combine the street-level and the area-based with highways models.  Use the latter in cases where response time is more important than precision and the former when the reverse is true.

Dispatcher User Interface (Usability)

The local area pickup and delivery system will leverage automated algorithms to improve operational effectiveness.  In spite of this, the dispatchers and dock foreman still play a pivotal role.  The dispatcher has the ability to constrain the routing and scheduling algorithms behavior, and the dispatcher is the point of contact with the on-road drivers.  In short, if the system is an airplane, then the dispatcher is the pilot and the scheduler is “auto pilot”.

Given the critical role that the dispatcher plays in the success of the system, the user interface must facilitate two outcomes which don’t necessarily pull in the same direction:

§       The system must be trivial to learn, and

§       Ease of learning cannot slow down experienced dispatcher

The motivation for the trivial to learn part is that training is a huge challenge.  Carriers have a limited number of people who are qualified to be a dispatcher, and they are essential to run the daily operation.  Furthermore, dispatchers typically work stressful 10 hour shifts, and it is usually difficult to teach new skills to an exhausted user.

The motivation for ease of use for an experienced dispatcher is that dispatching is a very fast-paced, no hesitation job.  A dispatcher is the front line of communication with drivers, and is constantly monitoring their status and making adjustments for unexpected situations (traffic congestion, inclement weather, vehicle troubles, and other sources of delay).  The system must facilitate this data gathering process, then simplify the dispatcher’s job of making and executing good decisions.

The main approach to this challenge is a client-server architecture, with the dispatcher application using a graphic display that overlays stop icons and driver route traces on a street map of the service territory.  The refresh speed of the graphic display is critical.  A high-end computer with an on-board graphics processor and dedicated graphics memory is essential.  Also, the dispatcher client either must run as a fat client, or a rich internet application (e.g. Adobe Flash/Flex).

Also essential to this approach are:

o      Point and click, drag and drop style of interaction; ideally using a touch-screen, optionally a mouse or other pointing device.

o      Ensuring that the display highlights the most significant information for dispatchers:

·       Muting the background display (streets, labels, landmarks)

·       Coordinating street density with map zoom level

·       Emphasizing unassigned stops, special service requirement stops, and stops that are nearing their service window close.

·       Suppressing the display of stops already serviced

Finally, since the scheduling algorithm could take several minutes to run, it is imperative that scheduling run asynchronously.  This creates a very interesting challenge because the dispatcher could be making different decisions than the scheduler when it comes to stop assignment and sequence.  How should these different actions be synchronized and reconciled?

The ease of learning and ease of use principles dictate that the dispatcher’s decisions must take priority.  There is nothing that would cripple a dispatcher’s confidence in a system more than to have the automated system reverse a decision.  The approach chosen to address this sub-challenge is:

o      Pass all dispatcher operations that change stops to the scheduler.

o      Have the scheduler detect these changes when the scheduler’s state machine processes events.

o      Identify changes that are different from those the scheduler made

·       Move the stop to the appropriate route at the closest position

·       Mark the stop as unable to be reassigned from the route.

·       If the route is not feasable, the problem will be corrected by the Scheduling heuristic.

Data Management

While there are several categories of data in this system, three of them pose the biggest challenge:

o      Street data.  As a rough estimate, a service territory with a 50 mile radius, covering a predominately urban/suburban area might include 150,000 streets and 1,000,000 blocks (over 500 cities and towns).

·       For address mapping purposes, the street name might occupy 6-8 MB.

·       For travel estimation purposes, the street segment data (including restrictions and time of day travel speeds) could occupy 25-30 MB.

o      Customer data.  A large Overnight Parcel site could have 100,000’s of customers.  This could translate to several hundred MB of data, not including indexes.

o      Stop data.  In principle this is small, since stop data changes from day to day, and only information for incomplete stops needs to be carried forward.  However, historical data for stops, over the past 6-12 months is extremely valuable for trend analysis and forecasting.

The archtectural approaches selected to manage this data are:

o      Customer data has relational usage patterns.

·       Generally, transactions are short

·       The primary access patterns are queries by ID, customer name, address, and city/zip code

·       Secondary access patterns include occasional add and update operations.

·       Relational databases are well-suited to these operations and the data size is not an obstacle.

o      Daily stop data is relatively small (under 1MB for 1000 stops) and is well suited for XML files.

·       The client and server components typically will maintain the full data set in memory as an object model

·       Stops can be transferred/persisted as an XML document.

·       If speed is an issue, the XML format can easily be replaced by a more efficient proprietary binary format.

o      For historical stop data, it makes sense to export the data on a daily basis to an OLAP (OnLine Analytical Processing) application.

o      Finally, street data requires a hybrid data management solution:

·       Store street name and block address data in relational format.

o      Access patterns for this data are queries against street name, city, and zip

o      Address ranges for blocks are searched, but only after matching on street name.

·       Store travel model data in a network format (i.e. each street segment maintains links to connecting street segments).  This approach allows all or part of the street network to be loaded into memory, and facilitates fast network traversals.

Conclusion: Observations on this Approach

The process described above explicitly treats the the choice of product line approach as the dominant complexity.  This is intentional for any system that has contexts with significant variations because:

o      Significant variations in context dependency often preclude a “one-size fits all” approach.  When such an approach is tried, stakeholders in one or more contexts are inevitably dissapointed.

o      Contextual differences are often pervasive, especially when one context has a different set of priorities than another.  It is difficult for SUV manufacturers to balance the priorities of city drivers and off-road enthusiasts.  Also, for a framework, components are very central to the principles of operation for the system.  Much of the rest of the system will depend on the framework approach.

o      Designing generalized components and architecting generalized frameworks are typically more difficult problems that designing specific solutions.

In summary, a high degree of complexity in all three of these areas is a very strong indicator that the  product line approach must be among the earliest architecture decisions.

This raises the question of how frequently a system faces multiple contexts.  The answer is a lot more frequently than you might imagine:

o      The obvious case when a system can be applied to multiple market segments.  Database technology, networking, and cellular communication all are examples.

o      Another case is when a firm chooses to address related market segments that have an obvious commonality.  One example of this are medical information systems (applicable to hospitals, clinics, and physician practices).  Another is a manufacturer of tools used in different phases of the semiconductor fabrication process.

o      The third and least obvious case is in products that are designed for a specific application.  In these cases, there still may be important differences between contexts, such as: user skill levels, mobility, network bandwidth, standards compliance, and security which can cause customer priorities to vary significantly.

Once you consider how ubiquitous context-sensitive development can be, and how difficult it is to design in support for this after the fact, you will be likely to agree that this complexity must be taken seriously as early in the process as possible.  The cost associated with considering it is much smaller than the cost of ignoring it.

Advertisements

1 Comment

  1. […] Complexity-Driven #4 […]

    Pingback by Complexity-Driven #4 article posted « Charlie Alfred’s Weblog — December 8, 2008 @ 8:34 pm


RSS feed for comments on this post. TrackBack URI

Create a free website or blog at WordPress.com.

%d bloggers like this: