Routing (Leaving Cert Applied Maths): Revision Notes

Routing

What is routing in dynamic programming?

Routing problems are a type of optimisation challenge where you need to find the best path through a network or sequence of decisions. In dynamic programming, routing involves determining the most efficient way to move between different states (locations or positions) over multiple time periods, whilst maximising benefits or minimising costs.

These problems are particularly useful for real-world scenarios like delivery routes, travel planning, resource allocation, and scheduling decisions where you must consider both immediate costs and future consequences.

Understanding the problem structure

Routing problems in dynamic programming are typically organised around several key components that work together to model decision-making over time. The network structure provides a visual framework for understanding how different elements connect and interact.

The network structure shows how different locations or states are connected, with possible paths between them. This visual representation helps us understand the relationships and available options at each stage of the decision process.

Problem setup and data organisation

Before solving a routing problem, you need to organise your information into clear data structures. This typically involves three types of information that must be carefully analysed: timing constraints, benefit calculations, and cost analysis.

The data organisation includes timing constraints (when certain options are available), benefit calculations (expected returns or profits from each choice), and cost analysis (expenses associated with moving between different states). Understanding how these elements interact is crucial for finding optimal solutions.

The backwards approach methodology

Dynamic programming routing problems use a backwards approach, which means you start from the final stage and work backwards to the beginning. This might seem counterintuitive, but it's actually the most logical way to ensure optimal decisions at each step.

Key components of the solution framework

Every routing problem involves five essential elements that form the structure of your solution. Understanding these components is crucial for setting up and solving any routing problem effectively.

Stage - This represents time periods or decision points in your problem. Stages are numbered based on how many time periods remain until the end.

State - These are the possible positions or locations you could be in at each stage. States represent all the viable options available at that point in time.

Action - These are the decisions you can make or the moves you can take from each state. Actions connect your current state to possible future states.

Destination - This shows where each action leads you. The destination becomes your new state in the next stage of the problem.

Value - This is the calculated benefit or cost of taking each action, including both immediate effects and future consequences.

The value calculation formula

The core calculation in routing problems follows a specific pattern that accounts for immediate gains, immediate costs, and future potential. This is the most important formula in routing problems:

The table shows how this calculation works in practice for the final stage, where OVD equals zero because there are no future stages to consider.

Step-by-step solution process

The solution process involves working through each stage systematically, building up from the final stage to the initial stage. This methodical approach ensures accuracy and completeness.

Finding the optimal solution

Once you've completed all stages, the optimal solution can be traced by following the asterisked (optimal) choices from the initial stage through to the final stage. This gives you the sequence of decisions that maximises your overall objective.

The optimal path considers both immediate benefits and long-term consequences, ensuring that short-term decisions don't compromise overall performance. This systematic approach guarantees that you find the truly best solution rather than just a locally optimal one.

Practical applications and exam tips

Routing problems appear frequently in Leaving Certificate Applied Mathematics because they demonstrate logical thinking and systematic problem-solving approaches. These skills transfer to many real-world decision-making scenarios.

Remember that routing problems can apply to many real-world contexts beyond the specific examples you study. The methodology remains consistent whether you're optimising travel routes, resource allocation, investment decisions, or scheduling problems.