I believe you need to take a higher-level view of matters.
Key is the GS1 system, previously known as EAN (which I use as I've used it for 20+ years.)
Important issue is that you should not allow YOUR shipment number to be dictated by an outside agency. If you decide to keep shipment details for 7 years say, and they decide to recycle numbers after 3, then you have a data problem. Equally, if you have more than one shipping agency (or take another on in the future, of the existing agency gets split into parts or sold or whatever) then again you can get a data problem when THEIR system changes.
(and that applies to ALL data not directly controlled by your organisation)
The EAN way is by using a SSCC - Serial Shipping Container Code. This is an 18-digit code assigned to an object and uniquely identifies that object. It has a nominal life of three years, so it should not be re-issued more frequently.
The SSCC is produced according to an internationally-recognised structure and encoded in a "code 128" barcode (hence it is often referred to as GS1-128 or EAN-128) which has a lead character of [fnc1] - internationally accepted to signify "This is a barcode following the EAN-128 format". The remaining characters are:
00
- AI for an SSCC (there is a whole slough of codes for various uses. "00" means "SSCC". It is actually an Application Identifier - though even barcode-printer manufacturers have been known to believe it forms part of a "20-digit code".
1 digit
- In former times, "3" was an "internal pallet" and "4" and "external pallet". Since the one often became the other, this system was quickly abandoned, but the legend persists - some will incorrectly insist that the leading digit must be a "3".
7-9 digits
- country code + organisation code. Allotted by the controlling organisation and licensed to the using member organisation.
9-7 digits
- individual shipment number issued by the using member organisation.
1 digit
- check digit produced according to the published algorithm and usually calculated by the printer firmware.
So the first and penultimate group of digits are allocated by the GS1-member organisation (ie your organisation) at their own discretion.
This system can be used for shipping your goods outside of your organisation and also for tracking the goods within your organisation.
In all probability, your shipper has allotted a subset of their numbers to you as they commonly do with small organisations that are not GS1 members. Unfortunately, the clerks performing this task prefer to treat all of their customers the same way, so the legend arises that you have to use their system. If this idea has taken root in the fertile minds of their IT monkeys, they may have set their system up on that assumption.
If their IT system has been set up by a professional, then they will be able to accept any complying SSCC - you simply send then your list of shipments issued with your numbers and their software will validate it against the label produced by your printer when the goods are picked up.
You'd really need to talk to their IT department on what their requirements are.
This would mean that you simply don't need to use their number at all - you can use the system as it was designed, using your numbers over which you have control.